欢迎访问LeetCode题解合集

题目描述

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

说明：

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

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

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

题解：

这题就是让从 1~9 中挑 k 个不重复的数字，使得和为 n 。

很明显，可以使用回溯。

由于不能有重复结果，那么就要确定枚举顺序。我们可以从小到大枚举，即上一个数选择 x ，那么下一个数从 x + 1 开始。

剪枝：如果当前还剩 t 次选择才能满足 k ，那么枚举的位置上界为 10 - t 。

有一些优化小技巧：

• n < k 是无解的
• k > 9 是无解的
• n > 45 是无解的

时间复杂度：$O(\binom{9}{k} * k)$

额外空间复杂度：$O(k)$

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
public:
    void dfs( int p, int now, int times) {
        if ( !now ) {
            if ( !times )
                ret.emplace_back( path );
            return;
        }
        for ( int i = p; i <= 10 - times; ++i ) {
            if ( now < i ) break;
            path.emplace_back( i );
            dfs( i + 1, now - i, times - 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        if ( n < k ) return {};
        if ( k > 9 ) return {};
        if ( n > 45 ) return {};
        dfs( 1, n, k );
        return ret;
    }
};
/*
时间：0ms，击败：100.00%
内存：6.2MB，击败：91.92%
*/