77. Combinations

Leetcode Backtracking

题目

Given two integers $n$ and $k$, return all possible combinations of $k$ numbers out of $1 ... n$.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

分析

非常明显的用backtracking的题目。

class Solution {
public:

    void combineHelper(int n, int k, int position, vector<int>& nums, vector<int>& chosen, vector<vector<int>>& res){
        if (chosen.size()==k){
            // base case
            res.push_back(chosen);
            return;
        }else{
            for (int i= position; i<n; i++){
                //choose
                chosen.push_back(nums[i]);
                // explore
                combineHelper(n, k, i+1, nums, chosen, res);
                // unchoose
                chosen.pop_back();
            }
        }
    }



    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> nums, chosen;
        // 初始化num为1...n
        for (int i=1; i< n+1; i++){
            nums.push_back(i);
        }
        combineHelper(n, k, 0, nums, chosen, res);
        return res;

    }
};

其实都不用nums数组，因为其nums[i]=i+1;

class Solution {
public:

    void combineHelper(int n, int k, int position, vector<int>& chosen, vector<vector<int>>& res){
        if (chosen.size()==k){
            // base case
            res.push_back(chosen);
            return;
        }else{
            for (int i= position; i<n; i++){
                //choose
                chosen.push_back(i+1);
                // explore
                combineHelper(n, k, i+1, chosen, res);
                // unchoose
                chosen.pop_back();
            }
        }
    }


    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> chosen;
        combineHelper(n, k, 0, chosen, res);
        return res;

    }
};