本题可以用递归+DFS的方式解决，我们假设一开始为3，对每个数的所有可能性进行遍历，不难得出这样一颗递归树

我们要做的，就是对这棵树进行DFS

我们先设置一个全局变量n，这是我们要输入的数据
然后设置一个状态数组state，来存储每个被遍历到的数字的状态，0为还没有选择，1为选定，2为放弃
private static int[] state=new int[16];//0未选，1选定，2放弃
private static int n;

然后我们开始写dfs函数，对这颗递归树进行搜索
private static void dfs(int k){
if(k>n){
for(int i=1;i<=n;i++)
if(state[i]==1)
sout(i+" ");
sout();
return;
//这一部分，是在进行一次到底端的搜索之后的输出。在下面的代码中，state[]中的数据将会被赋予两个值，也就是1和2，并对这两种情况分别进行递归（向下搜索），一直到搜索到尽头，这个时候。就遍历state[]，对其中值为1的位置所对应的数字输出（这里我们令i的初始值为1，这样就与state[]的下标对应上了），在遍历完一轮时候，换行，然后结束（返回上一层）
..................
}

private static void dfs(int k){
.................
//我们上面说，state[]中的数据将会被赋予两个值，这几行代码，就是给当前数字的状态赋值的，分别让它不取和取，然后对改变状态后的树继续搜索。搜索结束后，把state[]恢复原状，其中进入到dfs(k+1)的搜索后，照样会有对子状态的取值，这便实现了分支
state[k]=2;
dfs(k+1);
state[k]=0;
state[k]=1;
dfs(k+1);
state[k]=0;
}
main函数里比较简单，不再说了
public static void main(String[] args) throws IOException {
BufferedReader cin=new BufferedReader(new InputStreamReader(System.in));
String[] str=cin.readLine().split(" ");
n=Integer.parseInt(str[0]);
dfs(1);
}