Leetcode 78. 子集(回溯法)

1. 子集(回溯法)

class Solution {
    List<List<Integer>> output = new ArrayList();
    List<Integer> sub = new ArrayList();
    int n,k = 0;
    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        for(k = 0; k <= n; k++){
            sub.clear();
            backTrace(nums,0);
        }
        return output;
    }

    private void backTrace(int[] nums,int index){
        if(sub.size() == k)
            output.add(new ArrayList<Integer>(sub));
        else{
            for(int i = index;i<n;i++){
                sub.add(nums[i]);
                backTrace(nums,i+1);
                sub.remove(sub.size() - 1);
            }
        }
    }
}

总结

add（）的时候要注意，不要add引用。
回溯法也是一种递归，这种方法先把容器搞满，再一个一个退回。