39. Combination Sum - Medium

前往題目

想法

• 之前寫過，要用backtracking，試試這次能不能自己寫出來

思路

就差臨門一腳，沒注意到index需要被pass，不然每次都會從0開始，結果雖然都是對的但會有重複項

1. backtracking
2. 疊代所有數字，每次都傳新的sum以及當前index，如果如果sum等於target就加入，大於就直接return
3. 每次循環結束前都要移除最後一項，因為已經檢查過了

Code

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList<List<Integer>>();
        backtracking(candidates, target, new ArrayList<Integer>(), 0, 0);
        return res;
    }

    private void backtracking(int[] candidates, int target, List<Integer> curCand, int curSum, int idx) {
        if (curSum > target) return;

        if (curSum == target) {
            // 一定要new了之後把List實例化才加入，不然會是空的
            res.add(new ArrayList<Integer>(curCand));
            return;
        }

        // 用傳入的index當作起點
        for (int i = idx; i < candidates.length; ++i) {
            curCand.add(candidates[i]);
            backtracking(candidates, 
                            target, 
                            curCand, 
                            curSum + candidates[i],
                            i
            );
            
            // Eject
            curCand.remove(curCand.size() - 1);
        }
    }
}