216.组合总和3

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

这里的剪枝是：

  • 剩余数字数目不够 i<d
  • 最后的t<0
  • 即使剩余数字全选最大的，和也不够t，t>i+....+(i-d+1)

Solution

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    // 用于存储所有可能的组合结果的列表
    private final List<List<Integer>> ans = new ArrayList<>();
    // 用于存储当前路径的列表
    private final List<Integer> path = new ArrayList<>();
    // 需要选取的数字个数
    int k;

    // 主要方法，寻找所有 k 个数的组合，使其和为 n
    public List<List<Integer>> combinationSum3(int k, int n) {
        this.k = k;
        // 开始深度优先搜索，初始状态为数字 9 和目标和 n
        dfs(9, n);
        return ans;
    }

    // 深度优先搜索方法
    private void dfs(int i, int t) {
        // 还需要选取的数字个数
        int d = k - path.size(); 

        // 剪枝条件：如果剩余的和 t < 0 或者剩余的和 t 超过从 i 到 i-d+1 的 d 个数的和
        if (t < 0 || t > (i * 2 - d + 1) * d / 2) {
            return;
        }

        // 如果不需要再选取数字了，说明找到了一个合法的组合
        if (d == 0) {
            // 将当前路径添加到结果列表中
            ans.add(new ArrayList<>(path));
            return;
        }

        // 从当前数字 i 开始向下搜索
        for (int j = i; j >= d; j--) {
            // 将当前数字 j 添加到路径中
            path.add(j);
            // 继续搜索下一个数字，目标和减少 j
            dfs(j - 1, t - j);
            // 回溯，移除当前数字 j
            path.remove(path.size() - 1);
        }
    }
}