216.md

216. Combination Sum III

Leetcode link

解题思路

这道题要求我们求 k 个不重复的 1～9 所有可能组合成数字 n 的组合

这种题目我们可以用回溯的方式来做，直接上代码

C++

class Solution {
public:
    vector<vector<int>> res;
    int k;
    int n;
    vector<vector<int>> combinationSum3(int k, int n) {
        this->k = k;
        this->n = n;
        combination(1, {}, 0);
        return res;
    }
    
    void combination(int start, vector<int> arr, int sum) {
        if(arr.size()== k) {
            if(sum == n) {
                res.push_back(arr);
            }
            return;
        }
        
        for(int i = start;i<=min(n, 9);i++) {
            if(sum+1 <= n) {
                arr.push_back(i);
                combination(i+1, arr, sum+i);
                arr.pop_back();
            }
        }
    }
};

Javascript

var combinationSum3 = function(k, n) {
    let res =[];

    var combination = function(start, arr, sum) {
    	// 如果当前组合的数组长度恰好符合 k 个
    	if(arr.length === k) {
        // 数组恰好是所求的一种组合
        if(sum === n) {
            res.push(arr);
        }
        return;
    	}
    
    	for(let i= start;i<= Math.min(9, n);i++) {
        if(i + sum <= n) {
            arr.push(i);
            // 深拷贝，不然会影响到前面的递归
            combination(i+1, [...arr], i+sum);
            arr.pop();
        }
    	}
		}

    combination(1, [], 0);
    return res;
};