40. Combination Sum II - Medium

前往題目

想法

• 和今天稍早寫的另一題(90)一樣的套路

思路

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

這題很妙的是和第90一樣的做法，但90是不能取同一個subset即便順序不同，這個是不能取到取過的數字

總之這個技巧的核心就是相同的元素不要跳著選取

Code

技巧解析

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);

        res = new ArrayList<List<Integer>>();

        backtrack(candidates, target, new ArrayList<Integer>(), 0, 0);

        return res;
    }

    private void backtrack(int[] candidates, int target, List<Integer> comb, int sum, int idx) {
        if (sum == target) {
            res.add(new ArrayList<Integer>(comb));
            return;
        }
        
        if (sum > target) return;


        for (int i = idx; i < candidates.length; ++i) {
            // 不允許相同元素跳著選取，只能照著順序選取
            if (i>idx && candidates[i]==candidates[i-1])
                continue;
            comb.add(candidates[i]);
            backtrack(candidates, target, comb, sum + candidates[i], i + 1);
            comb.remove(comb.size() - 1);
        }
    }
}