Thinking process

how to avoid duplicates?

• how to check when to skip adding?
• if the previous one is equal to the current value, then skip adding current value

Mistakes

1. Don't forget to sort the array first

public class Solution {
    //[1,1]
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //validate input
        if (nums.length == 0) return result;
        Arrays.sort(nums);
        dfsHelper(nums, result, new ArrayList<Integer>(), 0);

        return result;
    }

    private void dfsHelper(int[] nums, List<List<Integer>> result, List<Integer> list, int index) {
        if (index > nums.length) return;

        result.add(new ArrayList<Integer>(list));

        for (int i = index; i < nums.length; ++i) {
            if (i > 0 && i != index && nums[i] == nums[i - 1]) continue;
            list.add(nums[i]);
            dfsHelper(nums, result, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}