216. Combination Sum III

,

Backtracking + DFS

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
26
27
28
29
30
class Solution {
    private static final int[] CANDIDATES = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        dfs(resultList, numList, 0, 0, k, n);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int i, int sum, int k, int targetSum) {
        if (sum > targetSum || numList.size() > k) {
            return;
        }
        if (i == CANDIDATES.length) {
            if (sum == targetSum && numList.size() == k) {
                resultList.add(new ArrayList<>(numList));
            }
            return;
        }

        // not choose
        dfs(resultList, numList, i + 1, sum, k, targetSum);

        // choose
        numList.add(CANDIDATES[i]);
        dfs(resultList, numList, i + 1, sum + CANDIDATES[i], k, targetSum);
        numList.remove(numList.size() - 1);
    }
}

以上从各个数字进行选与不选的角度来驱动搜索。

Backtracking + DFS

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
26
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        dfs(resultList, numList, 0, 1, k, n);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int sum, int startNumber, int k, int n) {
        if (sum == n) {
            if (numList.size() == k) {
                resultList.add(new ArrayList<>(numList));
            }
            return;
        }

        for (int number = startNumber; number <= 9; number++) {
            if (sum + number > n) {
                break;
            }
            numList.add(number);
            dfs(resultList, numList, sum + number, number + 1, k, n);
            numList.remove(numList.size() - 1);
        }
    }
}

以上将选择逻辑抽象为多叉树来进行搜索，其中 for 循环在同一层上进行选择，for 循环内部的 dfs 函数调用则为进入树的下一层节点。

References

216. Combination Sum III