LeetCode Combinations: DFS vs Iterative

Overview

This LeetCode Combinations could be solved by using backtracking/DFS: C(n,k) = C(n-1, k-1) U n + C(n-1,k) and it could be done in iterative way too.

LeetCode Combinations

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

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Analysis: DFS vs Iterative

1) DFS in standard way: Since we need to permute all the possible combinations, we could adopt the general framework of backtracking approach to do it: Suppose answer[k] is a general legal combination, we need to construct all the candidates for answer[0], … answer[k-1], backtracking is exactly the way to do this, and  remember to keep the candidates sorted to ensure there is no duplicates such as [1, 2] and [2, 1]. The following source code is accepted by LeetCode OJ to pass this Combinations problem:

class Solution {
    public:
        vector<vector<int> > ret;
        vector<int> ans;

        void dfs(int i, int k, int n) {
            if (i >= k) {
                ret.push_back(ans);
                return;
            };
            int s = 0;
            if (i > 0) s = ans[i - 1];
            for (int c = s + 1; c <= n; ++c) {
                ans[i] = c;
                dfs(i+1, k, n);
            }
        }

        vector<vector<int> > combine(int n, int k) {
            ans.resize(k);
            dfs(0, k, n);
            return ret;
        }
};

2) DFS by using the formula: select k numbers from a set of n numbers, from mathematical angle, we know the following formula:

C(n,k) = C(n-1, k-1) U n + C(n-1,k)

By implementing the above formula, the following code is accepted by LeetCode OJ to pass this Combinations problem too:

class Solution {
    public:
        vector<vector<int> > dfs(int k, int n) {
            vector<vector<int>>  ret;
            if (k == 1) {
                ret.resize(n);
                for (int i = 1; i <= n; ++i) ret[i - 1].push_back(i);
                return ret;
            }
            if (k == n) {
                vector<int> ans(n, 0);
                for (int i = 1; i <= n; ++i) ans[i-1] = i;
                ret.push_back(ans);
                return ret;
            }

            vector<vector<int>> p1 = dfs(k - 1, n - 1);
            for (auto it = p1.begin(); it != p1.end(); ++it)
                it->push_back(n);
            vector<vector<int>> p2 = dfs(k, n - 1);
            ret.insert(ret.end(), p1.begin(), p1.end());
            ret.insert(ret.end(), p2.begin(), p2.end());
        }

        vector<vector<int> > combine(int n, int k) {
            return dfs(k, n);
        }
};

3) Iterative Implementation: we could actually generate the subset level by level, first generate the subset of size 1, and then of size 2, this could be done by directly translating the dfs approach in (1) into iterative way, the following code could be accepted by LeetCode OJ to pass this Combinations problem as well:

class Solution {
public:
vector<vector<int> > combine(int n, int k) {
    vector<vector<int>> ret;
    ret.resize(n);
    for (int i = 0; i < n; ++i)
        ret[i].push_back(i + 1);
    for (int i = 1; i < k; ++i) {
        vector<vector<int>> newSub;
        for (int j = ret.size() - 1; j >= 0; --j) {
            ret[j].push_back(0);
            for (int k = ret[j][i - 1] + 1; k <= n; ++k) {
                ret[j][i] = k;
                newSub.push_back(ret[j]);
            }
        }
        ret = newSub;
    }
    return ret;
}
};

Summary

This LeetCode Combinations could be solved by using backtracking/DFS: C(n,k) = C(n-1, k-1) U n + C(n-1,k) and it could be done in iterative way too.

Written on April 14, 2013