NC27 集合的所有子集算法 java实现

题目描述

现在有一个没有重复元素的整数集合S，求S的所有子集
注意：
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素
示例1
输入：[1,2,3]
返回值：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

解题思路

所有子集的排列组合，就意味着要用dfs回溯了，这里只是简单的列举组合，因此还没涉及到剪枝操作，反而比较容易些。

代码实现

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        res.add(new ArrayList<Integer>());
        ArrayList<Integer> list=new ArrayList<Integer>();
        //由于需要有顺序，所以先对数组进行排序
        Arrays.sort(S);
        dfs(0,S,res,list);
        return res;
    }

    public void dfs(int start, int[] S, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list){
        if(start>=S.length){
            return;
        }

        for(int i=start;i<S.length;i++){
        	//不需要剪枝，直接存结果集
            list.add(S[i]);
            res.add(new ArrayList<Integer>(list));
            dfs(i+1,S,res,list);
            //退回一步
            list.remove(list.size()-1);
        }
    }
}