216. Combination Sum III。

xiaoxiao2021-02-28  27

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.

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]]


指定一个k和n,需要从1到9之间找到k个不重复的数字相加起来等于n,最后返回所有的可能性集合。


利用回溯的想法进行计算即可。从1开始遍历,然后向后找合适的数字放入数组中,当满足条件时则添加到答案中,不满足时则回溯一位继续进行计算。

class Solution { public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> ans;// 用来保存最后的答案 vector<int> comb;// 用来保存当前的分组 combination(ans,comb,k,1,n); return ans; } // 递归调用 void combination(vector<vector<int>>& ans,vector<int>& comb,int k,int start,int n) { if(comb.size() > k)// 结束 return; if(comb.size()==k&&n!=0)//结束 return; // 如果此时comb中的元素个数已经等于想要的;或者此时目标数为0,结束递归 if(comb.size() == k && n == 0) { ans.push_back(comb); return; } for(int i = start; i<=9&&i<=n; i++) { comb.push_back(i); combination(ans,comb,k,i+1,n-i);// 向下一个数字查找 comb.pop_back();// 回溯一位 } } };
转载请注明原文地址: https://www.6miu.com/read-2649996.html

最新回复(0)