www.4688comleetcode笔记:Combination Sum III

leetcode笔记:Combination Sum III

一. 主题素材陈诉

Find all possible combinations of k numbers that add up to a number n,
given that only numbers from 1 to 9 can be used and each combination
should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:
Input: k = 3, n = 7
Output:

[[1,2,4]]

Example 2:
Input: k = 3, n = 9
Output:

[[1,2,6], [1,3,5], [2,3,4]]

二. 标题分析

那道题题是构成之和层层的第三道题,跟从前两道Combination Sum
组合之和,前面两道题的联络比较紧凑,变化不大,而这道跟它们最鲜明的两样就是那道题须要多个解五月素的个数为k。

实在那道题是Combination Sum和Combination Sum

II的综合体,两者杂糅到一道正是那道题的解法了。n是k个数字之和,要是n<0,则直接重回,尽管n

0,并且此时有时组合temp中的数字个数正好为k,表明此时是一个方便的组合解,将其存入结果result中。

三. 示例代码

#include 
#include 
using namespace std;

class Solution {
public:
    vector > combinationSum3(int k, int n) {
        vector > result;
        vector temp;
        combinationSum3DFS(k, n, 1, temp, result);
        return result;
    }

private:
    void combinationSum3DFS(int k, int n, int level, vector &temp, vector > &result) {
        if (n < 0) return;
        if (n == 0 && temp.size() == k) result.push_back(temp);
        for (int i = level; i <= 9; ++i) {
            temp.push_back(i);
            combinationSum3DFS(k, n - i, i + 1, temp, result);
            temp.pop_back();
        }
    }
};

四. 小结

Combination Sum种类是杰出的DFS标题,还供给深切钻探。

Sum III 一. 标题陈说Find all possible combinations of k numbers that add up to a number n,
given that only numbers from 1 to 9 can be used and ea…

相关文章