39. Combination Sum

LeetCode

Backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(candidates, target, 0, 0);
        return result;
    }

    void backtracking(int[] candidates, int target, int sum, int startIndex) {
        if (sum > target) return;
        if (sum == target) {
            result.add(new ArrayList<>(path)); // copy the current path
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // remove the last one (backtracking)
        }

    }
}

Remarks:

  1. Remember that the numbers can be used for multiple times so in backtracking we set the next index i instead of i+1.
  2. Template for backtracking: 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void backTracking(params) {
     ...
     if (endCondition) {
       saveResult();
       return;
     }
     ...
     backTracking(nextParams);
     ...
    }