MENU

LeetCode77. Combinations(递归 / 回溯)

2019 年 04 月 13 日 • 阅读: 898 • LeetCode阅读设置

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();
        }
    }
};
最后编辑于: 2022 年 02 月 05 日