Poison

216. Combination Sum III

发表于
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
26
27
28
29
30
31
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 num, int k, int n) {
        if (sum > n) {
            return;
        }
        if (sum == n) {
            if (numList.size() == k) {
                resultList.add(new ArrayList<>(numList));
            }
            return;
        }
        if (num > 9) {
            return;
        }

        // not choose
        dfs(resultList, numList, sum, num + 1, k, n);

        // choose
        numList.add(num);
        dfs(resultList, numList, sum + num, num + 1, k, n);
        numList.remove(numList.size() - 1);
    }
}

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

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
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 函数调用则为进入树的下一层节点。

Reference

216. Combination Sum III