216. Combination Sum III ------------M

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 = 7
Output: [[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

A:
就是递归

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        return helper(k, 1, n);
    }
private:
    vector<vector<int>> helper(int k , int startVal, int n){
        vector<vector<int>> res;
        if(startVal > n || k <=0 ) // to prevent stack overflow
            return res;
        
        if(k ==1){
            if(n >= startVal && n <= 9)
                res.push_back(vector<int>{n});
        }else{
            res = helper(k, startVal+1, n);
            auto subRes = helper(k-1, startVal+1, n-startVal);
            for(auto v: subRes){
                v.push_back(startVal);
                res.push_back(v);
            }
        }
        return res;
    }
};

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        return helper( 1,k,n);
    }
    private List<List<Integer>> helper( int start, int k, int n){
        List<List<Integer>> all = new LinkedList<List<Integer>>();
        if(k == 1){
            if(n >= start && n<= 9){
                List<Integer> tmp = new LinkedList();
                tmp.add(n);
                all.add(tmp);
            }
            return all;
        }
        for(int i = start;i<= Math.min(n,9) ; i++){
            List<List<Integer>> oneLess = helper(i+1,k-1,n-i);
            for(List<Integer> list:oneLess)
                list.add(0,i);            
            all.addAll(oneLess);
        }
        return  all;
    }
}

Mistakes:
1: 一开始 没有注意限制条件  1---9的意思。