LeetCode77. Combinations（递归 / 回溯）

LeetCode77. Combinations（递归 / 回溯）

• Medium
• Accepted：193,768
• Submissions：413,947

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],
]

链接

https://leetcode.com/problems/combinations

题意

给定两个整数n和k，找到1到n中k个数的所有可能组合。

题解

也是组合问题，和之前的LeetCode46. Permutations（递归 / 回溯）很类似。

对于n=4和k=2，我们可以先选择1然后可以分别选择2、3、4得到12、13、14，再选择2后分别选择3、4得到23、24。

使用自顶向下的递归即可，需要注意的是递归回溯之后有一个“还原”的处理，也就是之前添加的元素需要删除。

事实上在递归过程的循环中，我们没有必要每次都遍历到最后一个数，比如说上图中的4，这时已经无法得到可行解了，所以可以添加一个小的剪枝。当前已经得到的元素数量为comb.size()，还需要k-comb.size()个元素，随意我们需要保证i循环到的位置还有k-comb.size()个元素，那么i <= n - (k - comb.size()) + 1。

时间复杂度：$O(k * C(n, k))$。

代码

• Runtime: 88 ms, faster than 62.27% of C++ online submissions for Combinations.
• Memory Usage: 12.8 MB, less than 39.01% of C++ online submissions for Combinations.

class Solution {
private:
    vector <vector<int>> ans;
    void solve(int n, int k, int start, vector <int> & comb)
    {
        if (comb.size() == k)
        {
            ans.push_back(comb);
            return ;
        }
        for (int i = start; i <= n; ++i)
        {
            comb.push_back(i);
            solve(n, k, i + 1, comb);
            comb.pop_back(); // 回溯
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        ans.clear();
        if (n == 0 || k == 0)
            return ans;
        vector <int> comb;
        solve(n, k, 1, comb);
        return ans;
    }
};

• Runtime: 64 ms, faster than 92.56% of C++ online submissions for Combinations.
• Memory Usage: 12.8 MB, less than 38.63% of C++ online submissions for Combinations.

class Solution {
private:
    vector <vector<int>> ans;
    void solve(int n, int k, int start, vector <int> & comb)
    {
        if (comb.size() == k)
        {
            ans.push_back(comb);
            return ;
        }
        for (int i = start; i <= n - (k - comb.size()) + 1; ++i) // 剪枝
        {
            comb.push_back(i);
            solve(n, k, i + 1, comb);
            comb.pop_back(); // 回溯
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        ans.clear();
        if (n == 0 || k == 0)
            return ans;
        vector <int> comb;
        solve(n, k, 1, comb);
        return ans;
    }
};

• Runtime: 55 ms, faster than 33.22% of C++ online submissions for Combinations.
• Memory Usage: 18 MB, less than 32.92% of C++ online submissions for Combinations.

class Solution
{
public:
    vector<vector<int>> combine(int n, int k)
    {
        vector<vector<int>> result;
        if (n == 0 || k == 0)
            return result;
        vector<int> subset;
        getSubsets(n, k, 1, subset, result);
        return result;
    }
    void getSubsets(int &n, int &k, int index, vector<int> &subset, vector<vector<int>> &result)
    { 
        if (subset.size() == k)
        {
            result.push_back(subset);
            return ;
        }
        else if (index <= n)
        {
            // 不选
            getSubsets(n, k, index + 1, subset, result);
            // 选
            subset.push_back(index);
            getSubsets(n, k, index + 1, subset, result);
            subset.pop_back();
        }
    }
};