Medium

题目描述

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

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

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

示例 1:

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

示例 2:

输入: 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
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是 1+2+3+4 = 10，因为 10 > 1，没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

解题思路

解题思路

这是一道典型的回溯算法题目。我们需要从数字 1-9 中选择 k 个不重复的数字，使其和等于 n。

核心思路：

  1. 使用回溯法枚举所有可能的组合
  2. 从数字 1 开始，依次尝试加入当前数字到组合中
  3. 递归处理剩余的数字选择，直到组合长度达到 k
  4. 当组合长度为 k 且和为 n 时，找到一个有效组合

剪枝优化：

  1. 当当前和已经超过目标值 n 时，直接返回
  2. 当剩余数字不足以构成 k 个数的组合时，直接返回
  3. 当剩余的最小可能和都大于目标值时，直接返回

算法步骤：

  1. 定义递归函数 backtrack(start, path, current_sum)
  2. 边界条件：当 path 长度等于 k 时，检查 current_sum 是否等于 n
  3. 从 start 开始遍历数字 1-9，将数字加入 path，递归调用
  4. 回溯：移除刚加入的数字，继续下一个数字的尝试

代码实现

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(1, k, n, path, result);
        return result;
    }
    
private:
    void backtrack(int start, int k, int target, vector<int>& path, vector<vector<int>>& result) {
        if (path.size() == k) {
            if (target == 0) {
                result.push_back(path);
            }
            return;
        }
        
        for (int i = start; i <= 9; i++) {
            if (i > target) break; // 剪枝：当前数字已经大于剩余目标值
            
            path.push_back(i);
            backtrack(i + 1, k, target - i, path, result);
            path.pop_back();
        }
    }
};

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        
        def backtrack(start, path, target):
            if len(path) == k:
                if target == 0:
                    result.append(path[:])
                return
            
            for i in range(start, 10):
                if i > target:
                    break
                
                path.append(i)
                backtrack(i + 1, path, target - i)
                path.pop()
        
        backtrack(1, [], n)
        return result

public class Solution {
    public IList<IList<int>> CombinationSum3(int k, int n) {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> path = new List<int>();
        Backtrack(1, k, n, path, result);
        return result;
    }
    
    private void Backtrack(int start, int k, int target, List<int> path, IList<IList<int>> result) {
        if (path.Count == k) {
            if (target == 0) {
                result.Add(new List<int>(path));
            }
            return;
        }
        
        for (int i = start; i <= 9; i++) {
            if (i > target) break;
            
            path.Add(i);
            Backtrack(i + 1, k, target - i, path, result);
            path.RemoveAt(path.Count - 1);
        }
    }
}

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const result = [];
    
    function backtrack(start, path, remaining) {
        if (path.length === k) {
            if (remaining === 0) {
                result.push([...path]);
            }
            return;
        }
        
        for (let i = start; i <= 9; i++) {
            if (i > remaining) break;
            path.push(i);
            backtrack(i + 1, path, remaining - i);
            path.pop();
        }
    }
    
    backtrack(1, [], n);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(C(9,k) × k) = O(9! / ((9-k)! × k!) × k)，其中 C(9,k) 是从9个数中选k个数的组合数，k 是每个组合的复制开销
空间复杂度O(k)，递归栈深度最大为 k，path 数组最大长度为 k

相关题目