Problem Description
How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, ...., sn} ? For example, we assume that S = {1, 2, 3}, and you can find seven nondecreasing subsequences, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
Input
The input consists of multiple test cases. Each case begins with a line containing a positive integer n that is the length of the sequence S, the next line contains n integers {s1, s2, s3, ...., sn}, 1 <= n <= 100000, 0 <= si <= 2^31.
Output
For each test case, output one line containing the number of nondecreasing subsequences you can find from the sequence S, the answer should % 1000000007.
Sample Input
3
1 2 3
Sample Output
7
http://blog.csdn.net/jingdianitnan/article/details/38019617
static long sum = 0;
public static void combination(int []a,int restCount,int count,int[] b,int pos){
if(restCount <= 0 || count > a.length){
return;
}
StringBuilder sb = new StringBuilder();
for(int i = pos;i >= restCount - 1;i-- ){
b[restCount - 1] = a[i];
if(restCount - 1 == 0){
sum++;
}
combination(a, restCount-1, count, b, i-1);
}
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
int n ;
Scanner in = new Scanner(System.in);
n = in.nextInt();
int[] s = new int [n];
for (int j = 0; j < s.length; j++) {
s[j] = in.nextInt();
}
for (int i = 0; i < s.length; i++) {
int[] b = new int[i+1];
combination(s, i+1, i+1, b, s.length - 1);
}
System.out.println(sum);
}
重新答一下，忘记去重了
static List<String> list = new ArrayList<String>();
public static void combination(int []a,int restCount,int count,int[] b,int pos){
if(restCount <= 0 || count > a.length){
return;
}
for(int i = pos;i >= restCount - 1;i-- ){
StringBuilder sb = new StringBuilder();
b[restCount - 1] = a[i];
if(restCount - 1 == 0){
for(int j:b){
sb.append(j);
}
if (!list.contains(sb.toString())) {
list.add(sb.toString());
}
}
combination(a, restCount-1, count, b, i-1);
}
}
public static void main(String[] args) {
int n ;
Scanner in = new Scanner(System.in);
n = in.nextInt();
int[] s = new int [n];
for (int j = 0; j < s.length; j++) {
s[j] = in.nextInt();
}
for (int i = 0; i < s.length; i++) {
int[] b = new int[i+1];
combination(s, i+1, i+1, b, s.length - 1);
}
System.out.println(list.size());
}