90. Subsets II - Medium

前往題目

想法

• 以為是簡單的backtrack，但是需要考慮如何防止加入重複的subset

思路

1. 先sort，這樣才好判斷相同的數字
2. 正常backtrack
3. 唯一需要注意的是追蹤index，如果循環中的index已經比傳入的index還大的時候就要判斷是否和前一個數字一樣，要跳過

判斷的邏輯很妙，尤其是i > idx，後來想了想應該是i == idx的時候不用判斷，因為還沒加入，加入後下一個循環就要看是否和上一個循環的數字一樣了

T: $O(n * 2^n)$，因為每一個可能都要列出來，只是把重複的跳過而已，有n個數字，每個都要決定加入或不加入，也就是兩個選擇

Code

class Solution {
    List<List<Integer>> res;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        res = new ArrayList<List<Integer>>();
        
        backtrack(nums, new ArrayList<Integer>(), 0);

        return res;
    }

    private void backtrack(int[] nums, List<Integer> comb, int idx) {
        res.add(new ArrayList<Integer>(comb));

        for (int i = idx; i < nums.length; ++i) {
            // skip duplicate number
            if (i > idx && nums[i] == nums[i - 1]) {
                continue;
            }
            comb.add(nums[i]);
            backtrack(nums, comb, i + 1);
            comb.remove(comb.size() - 1);
        }
    }
}