QUESTION:

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

EXPLANATION:

还是backtracking的问题

就是1-2-3 2-3 3这样的顺序

我写的逻辑就比较复杂，我是添加了所有的可能组合，并且顺序不一样也算不重复的。

伪代码是：

length=0 length=1 length=2的时候，这样的所有组合，然后取出重复的就可以。

SOLUTION:

class Solution {
    List<List<Integer>> subsetsResult = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<Integer> tmp = new ArrayList<>();
        ArrayList<Integer> integers = new ArrayList<>();
        for(int i = 0;i<nums.length;i++) integers.add(nums[i]);
        for(int i = 0;i<integers.size();i++) subsetsHelper(integers,tmp,i);
        subsetsResult.add(integers);
        return subsetsResult;
    }
    public void subsetsHelper(List<Integer> list,List<Integer> tmp,int length){
        if(tmp.size()==length){
            subsetsResult.add(new ArrayList<>(tmp));
        }else {
            for(int i =0;i<list.size();i++){
                if(tmp.size()>=1&&list.get(i)<tmp.get(tmp.size()-1))continue;
                Integer removed = list.remove(i);
                tmp.add(removed);
                subsetsHelper(list,tmp,length);
                tmp.remove(tmp.size()-1);
                list.add(i,removed);
            }
        }
    }
}



class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> subset = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        dfsHelper(nums, 0, subset, result);
        return result;
    }
    
    private void dfsHelper(int[] nums, int start, List<Integer> subset, List<List<Integer>> result) {
        result.add(new ArrayList<Integer>(subset));
        
        for (int i = start; i < nums.length; i++) {
            subset.add(nums[i]);
            dfsHelper(nums, i + 1, subset, result);
            subset.remove(subset.size() - 1);
        }
    }
}