本文共 1709 字,大约阅读时间需要 5 分钟。
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]]
递归思想的经典运用!
combination函数有一点不太好理解if(k==0&&n==0)//递归结束条件 { res.push_back(path);//加入path } for(int i=start;i<=10-k&&i<=n;i++)//i表示加入第一个元素是i,另外k-1个在其后面,所以i的最大值是10-k,因为10-k后面最多有k-1个值。 { path.push_back(i);//加入,紧接着调用组合个数为k-1,开始为i+1的递归 combination(res,path,i+1,k-1,n-i);// path.pop_back();//这个是表示把i去掉,重新开始以i+1的组合。因为上一步的递归调用已经把i开始的所有组合都列举完了。 }
首先递归先写出其终止条件,这个比较简单。
其次,写下次要递归的, 注意i的终止条件是小于等于10-k,且小于等于n,10-k的原因是i只能取1,..,9,一旦i选定之后,后面至少要有k-1个不同的,所以9-(k-1)=10-k,即i不能大于10-k,否则,以i开始,再找k-1个ascending,unique的数,肯定会超过9的。 循环里,先把当前的i加入,之后递归调用combination。最后再把i移除(这个要好好理解!),循环i+1。class Solution { //递归解决问题的有一个典型例子public: vector> combinationSum3(int k, int n) { vector > res; vector path; if(k>=10||k<=0||n<=0||n>45) return res; combination(res,path,1,k,n); return res; }private: void combination(vector > &res,vector &path,int start,int k,int n)//path是存放一次合理的组合 //statt是表示以start开始的组合,k表示k个数,n表示总和为n { if(k==0&&n==0)//递归结束条件 { res.push_back(path);//加入path } for(int i=start;i<=10-k&&i<=n;i++)//i表示加入第一个元素是i,另外k-1个在其后面,所以i的最大值是10-k,因为10-k后面最多有k-1个值。 { path.push_back(i);//加入,紧接着调用组合个数为k-1,开始为i+1的递归 combination(res,path,i+1,k-1,n-i);// path.pop_back();//这个是表示把i去掉,重新开始以i+1的组合。因为上一步的递归调用已经把i开始的所有组合都列举完了。 } }};
转载地址:http://vexvi.baihongyu.com/