216. Combination Sum III

Problem from leetcode 216. Combination Sum III

---

这道题是39. Combination Sum和40. Combination Sum II的简化版。

---

class Solution {
public:
    vector<vector<int> > combinationSum3(int k, int n) {
        vector<vector<int> > result;
        vector<int> cur(k);
        dfs(k, n, 0, 1, 0, cur, result);
        return result;
    }
    void dfs(int k, int n, int pos, int digit, int curSum, vector<int> &cur, vector<vector<int> > &result)
    {
        if(pos == k)
        {
            if(curSum == n) result.push_back(cur);
            return;
        }
        if(digit > 9 || curSum > n) return;
        dfs(k, n, pos, digit+1, curSum, cur, result);
        cur[pos] = digit;
        dfs(k, n, pos+1, digit+1, curSum+digit, cur, result);
    }
};

Java:

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        ArrayList<Integer> cur = new ArrayList<Integer>();
        dfs(k, n, 0, 1, 0, cur, result);
        return result;
    }
    public void dfs(int k, int n, int pos, int digit, int curSum, ArrayList<Integer> cur, List<List<Integer>> result)
    {
        if(pos == k)
        {
            if(curSum == n) result.add(new ArrayList<Integer>(cur));
            return;
        }
        if(pos >= k || curSum > n || digit > 9) return;
        dfs(k, n, pos, digit+1, curSum, cur, result);
        cur.add(digit);
        dfs(k, n, pos+1, digit+1, curSum+digit, cur, result);
        cur.remove(cur.size()-1);
    }
}

Python:

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        result, cur = [], [0]*k
        self.dfs(k, n, 0, 1, 0, cur, result)
        return result
        
    def dfs(self, k, n, pos, digit, curSum, cur, result):
        if pos == k:
            if curSum == n: result.append(list(cur))
            return
        if pos >= k or curSum > n or digit > 9: return
        self.dfs(k, n, pos, digit+1, curSum, cur, result)
        cur[pos] = digit
        self.dfs(k, n, pos+1, digit+1, curSum+digit, cur, result)