Leetcode 77- Combination（回溯）

题意

求 C(n,k)

思路

算法1

二进制枚举状态。

回溯法

为了避免重复，当第i位为m时，i + 1后的位都在[m + 1, n]之间取。

比如n = 4, k = 2。先枚举第一位为1，然后之后的1位数在[2, 4]之间取。当第一位为2，之后的1位数在[3, 4]之间取…。

代码

algorithm 1

class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> ans; for (int s = 0; s < (1 << n); s++) { if (__builtin_popcount(s) == k) { vector<int> v; for (int i = 0; i < n; i++) { if (s & (1 << i)) v.push_back(i + 1); } ans.push_back(v); } } return ans; } };

algorithm 2

class Solution { private: int LIMIT, n; vector<vector<int>> ans; public: void dfs(int step, vector<int>& a) { if (step == LIMIT) { ans.push_back(a); return; } int x = a.back(); for (int i = x + 1; i <= n; i++) { a.push_back(i); dfs(step + 1, a); a.pop_back(); } } vector<vector<int>> combine(int n, int k) { LIMIT = k; this->n = n; vector<int> a; for (int i = 1; i <= n; i++) { a.push_back(i); dfs(1, a); a.pop_back(); } return ans; } };