【思路】
dfs(int m, int cnt,String s)
表示当前选到m(最大可以选到n),还可以再选cnt个,当前选的组合用s记录。
时间复杂度:
每个数有两种选择:选或者不选。因此又有2^n种状态,每种状态计算量为O(1)。因此时间复杂度为O(2^n)
import java.util.Scanner;
class Main{
static int n;
//static int a[];
public static void dfs(int m, int cnt,String s){
if(m > n){//最后一个数了
if(cnt == 0){
//去掉前面的空格
System.out.println(s.substring(1,s.length()));
return;
}
return;
}
dfs(m + 1, cnt - 1, s +" "+ m);//选m
dfs(m + 1, cnt, s); //不选m
}
public static void main(String args[]){
Scanner reader = new Scanner(System.in);
System.out.println();
n = reader.nextInt();
//从n个数中选择i个
for(int i = 1; i <= n; i++)
dfs(1, i, "");
}
}
终于找着一个我这个菜鸡看得懂的题解了
加油 ~~