LeetCode-216. Combination Sum III

LeetCode-216. 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.

Note:

All numbers will be positive integers.The solution set must not contain duplicate combinations.

Example 1:

Input: k = 3, n = 7Output: [[1,2,4]]

Example 2:

Input: k = 3, n = 9Output: [[1,2,6], [1,3,5], [2,3,4]]

题解：

class Solution {public: void dfs(int now, int sum, vector> &res, vector &tmp, int n, int k, vector &visit) { if (sum == n && k == 0) { res.push_back(tmp); } else if (sum < n) { for (int i = 1; i <= 9; i++) { if (visit[i] == false && i >= now) { tmp.push_back(i); visit[i] = true; dfs(i, sum + i, res, tmp, n, k - 1, visit); visit[i] = false; tmp.pop_back(); } } } } vector> combinationSum3(int k, int n) { if (k >= n) { return {}; } vector> res; vector tmp; vector visit(n - 2, false); dfs(1, 0, res, tmp, n, k, visit); return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。