江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第216题：组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件： - 只使用数字1到9 - 每个数字最多使用一次 返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

题目描述

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

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

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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

解题思路

这是一个组合问题，可以使用回溯算法解决。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法，如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来舍弃该解，即回溯并且尝试另一种可能。

针对本题，我们有以下解题思路：

方法一：回溯法（Backtracking）

回溯法是解决这类组合问题的标准方法，我们通过以下步骤解决：

  1. 定义一个回溯函数，参数包括：当前组合、目标和n的剩余值、已使用的数字个数k、起始数字
  2. 在回溯函数中，我们有三种情况：
    • 如果k = 0且n = 0，说明找到了一个有效组合，将其加入结果集
    • 如果k = 0或n < 0，说明当前组合不满足条件，直接返回
    • 否则，从起始数字开始尝试每个可能的数字（范围是1-9）
  3. 对于每个尝试的数字i，我们将其加入当前组合，递归调用回溯函数（参数为：当前组合、n-i、k-1、i+1）
  4. 回溯时，将最后加入的数字从组合中移除，尝试下一个数字

这种方法会遍历所有可能的组合，并筛选出满足条件的组合。

方法二：位运算（Bit Manipulation）

由于本题的数字范围非常有限（仅使用1-9），我们也可以使用位运算来模拟组合的生成：

  1. 使用一个9位的二进制数表示选择状态，第i位为1表示选择了数字i+1
  2. 枚举所有可能的选择状态（最多有2^9种）
  3. 对于每种状态，检查是否恰好选择了k个数字，且它们的和为n
  4. 如果满足条件，将该组合加入结果集

这种方法的时间复杂度为O(2^9)，对于本题的规模来说是可接受的。

代码实现

C# 实现

public class Solution {
    // 回溯法实现
    public IList<IList<int>> CombinationSum3(int k, int n) {
        List<IList<int>> result = new List<IList<int>>();
        Backtrack(result, new List<int>(), k, n, 1);
        return result;
    }
    
    private void Backtrack(List<IList<int>> result, List<int> current, int k, int remain, int start) {
        // 如果已经选择了k个数字且剩余和为0，找到一个有效组合
        if (k == 0 && remain == 0) {
            result.Add(new List<int>(current));
            return;
        }
        
        // 提前剪枝：如果k小于0或remain小于0，无法构成有效组合
        if (k <= 0 || remain <= 0) {
            return;
        }
        
        // 从start到9尝试每个数字
        for (int i = start; i <= 9; i++) {
            // 尝试选择当前数字
            current.Add(i);
            // 递归寻找下一个数字
            Backtrack(result, current, k - 1, remain - i, i + 1);
            // 回溯，移除当前数字，尝试其他可能
            current.RemoveAt(current.Count - 1);
        }
    }
    
    // 位运算实现
    public IList<IList<int>> CombinationSum3BitManipulation(int k, int n) {
        List<IList<int>> result = new List<IList<int>>();
        
        // 遍历所有可能的组合（使用位掩码表示）
        for (int mask = 0; mask < (1 << 9); mask++) {
            // 检查是否恰好选择了k个数字
            if (CountBits(mask) == k) {
                // 计算所选数字的和
                int sum = 0;
                List<int> combination = new List<int>();
                
                for (int i = 0; i < 9; i++) {
                    if ((mask & (1 << i)) != 0) {
                        combination.Add(i + 1);
                        sum += (i + 1);
                    }
                }
                
                // 检查和是否等于n
                if (sum == n) {
                    result.Add(combination);
                }
            }
        }
        
        return result;
    }
    
    // 计算二进制数中1的个数
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

Python 实现

class Solution:
    # 回溯法实现
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        self.backtrack(result, [], k, n, 1)
        return result
    
    def backtrack(self, result, current, k, remain, start):
        # 如果已经选择了k个数字且剩余和为0，找到一个有效组合
        if k == 0 and remain == 0:
            result.append(current[:])
            return
        
        # 提前剪枝：如果k小于0或remain小于0，无法构成有效组合
        if k <= 0 or remain <= 0:
            return
        
        # 从start到9尝试每个数字
        for i in range(start, 10):
            # 尝试选择当前数字
            current.append(i)
            # 递归寻找下一个数字
            self.backtrack(result, current, k - 1, remain - i, i + 1)
            # 回溯，移除当前数字，尝试其他可能
            current.pop()
    
    # 位运算实现
    def combinationSum3BitManipulation(self, k: int, n: int) -> List[List[int]]:
        result = []
        
        # 遍历所有可能的组合（使用位掩码表示）
        for mask in range(1 << 9):
            # 检查是否恰好选择了k个数字
            if bin(mask).count('1') == k:
                # 计算所选数字的和
                combination = []
                sum_val = 0
                
                for i in range(9):
                    if mask & (1 << i):
                        combination.append(i + 1)
                        sum_val += (i + 1)
                
                # 检查和是否等于n
                if sum_val == n:
                    result.append(combination)
        
        return result

C++ 实现

class Solution {
public:
    // 回溯法实现
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(result, current, k, n, 1);
        return result;
    }
    
private:
    void backtrack(vector<vector<int>>& result, vector<int>& current, int k, int remain, int start) {
        // 如果已经选择了k个数字且剩余和为0，找到一个有效组合
        if (k == 0 && remain == 0) {
            result.push_back(current);
            return;
        }
        
        // 提前剪枝：如果k小于0或remain小于0，无法构成有效组合
        if (k <= 0 || remain <= 0) {
            return;
        }
        
        // 从start到9尝试每个数字
        for (int i = start; i <= 9; i++) {
            // 尝试选择当前数字
            current.push_back(i);
            // 递归寻找下一个数字
            backtrack(result, current, k - 1, remain - i, i + 1);
            // 回溯，移除当前数字，尝试其他可能
            current.pop_back();
        }
    }
    
public:
    // 位运算实现
    vector<vector<int>> combinationSum3BitManipulation(int k, int n) {
        vector<vector<int>> result;
        
        // 遍历所有可能的组合（使用位掩码表示）
        for (int mask = 0; mask < (1 << 9); mask++) {
            // 检查是否恰好选择了k个数字
            if (__builtin_popcount(mask) == k) {
                // 计算所选数字的和
                int sum = 0;
                vector<int> combination;
                
                for (int i = 0; i < 9; i++) {
                    if (mask & (1 << i)) {
                        combination.push_back(i + 1);
                        sum += (i + 1);
                    }
                }
                
                // 检查和是否等于n
                if (sum == n) {
                    result.push_back(combination);
                }
            }
        }
        
        return result;
    }
};

性能分析

各语言实现的性能对比：

实现语言 执行用时 内存消耗 特点
C# 96 ms 25.8 MB 回溯法实现简洁，位运算实现较为高效
Python 36 ms 13.9 MB Python的列表操作方便，适合回溯算法
C++ 0 ms 6.7 MB 性能最优，尤其是位运算实现非常高效

补充说明

代码亮点

  1. 回溯法中使用了剪枝条件（k <= 0 || remain <= 0），提前结束不可能的分支，优化了时间复杂度
  2. 位运算实现利用了二进制表示选择状态，使得代码更简洁
  3. C++实现中使用了内置函数__builtin_popcount计算位数，简化了代码
  4. 对于每种实现，我们都确保了不会产生重复组合，这是因为我们每次选择数字时都从前一个数字的下一个开始

优化方向

  1. 可以增加更多的剪枝条件，例如当剩余的数字不足以组成k个数或剩余和太大无法达成时，可以提前返回
  2. 在回溯过程中，可以先排序可选数字，以便更好地剪枝
  3. 对于位运算实现，可以进一步优化遍历范围，只考虑含有k个1的位掩码

解题难点

  1. 理解回溯算法的核心思想和实现细节
  2. 正确处理组合条件，确保每个数字最多使用一次
  3. 避免生成重复组合
  4. 有效剪枝以提高算法效率

常见错误

  1. 忘记检查选择的数字个数是否为k
  2. 忘记回溯（移除当前尝试的数字）
  3. 不正确的递归终止条件
  4. 在生成组合时没有避免重复

相关题目