leetcode 链接：216. 组合总和 III

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例：

  1. 输入: k = 3, n = 7
  2. 输出: [[1,2,4]]
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

解答 & 代码

递归回溯

class Solution {
private:
    void findCombinations(int k, int target, int left, vector<int>& result, vector<vector<int>>& resultList)
    {
        // 递归结束条件：如果剩余需要的数字数 k<=0，直接返回
        if(k <= 0)
            return;

        // 从左边界遍历元素
        for(int i = left; i <= 9 && i <= target; ++i)
        {
            result.push_back(i);    // 选取当前元素

            // 如果当前只需要一个数字且当前元素值等于目标值，将当前组合存入结果数组
            if(k == 1 && i == target)
                resultList.push_back(result);
            else    // 递归或取组合的下一个元素
                findCombinations(k - 1, target - i, i + 1, result, resultList);

            result.pop_back();        // 回溯
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> result;
        vector<vector<int>> resultList;
        findCombinations(k, n, 1, result, resultList);
        return resultList;
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6.3 MB, 在所有 C++ 提交中击败了 51.86% 的用户