18. Subsets II

public class Solution {
    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // write your code here
       
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> prev = new ArrayList<>();
        helper(prev, 0, nums, rst);
        return rst;
    }
   
    private void helper(List<Integer> subset, int start, int[] nums, List<List<Integer>> rst) {
        rst.add(new ArrayList<Integer>(subset));
        for(int i = start; i < nums.length; i++) {
            if (i != start && nums[i]==nums[i-1]) {
                continue;
            }
            List<Integer> cur = new LinkedList<>(subset);
            cur.add(nums[i]);
            helper(cur, i+1, nums, rst);
            // [1,2] -> [1]  回溯
            cur.remove(cur.size() - 1);
        }
    }
   
   
   
}