Combination Algorithm by Iterative Backtracking Algorithm

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

From this post, we have the recursive algorithm to pick the i-th element and all we have to do it so pick k-i elements in the remaining set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    void combine(int n, int k, vector<vector<int>> &r, vector<int> &nums) {
        for (int i = n; i >= k; --i) {
            nums[k - 1] = i;
            if (k > 1) {
                combine(i - 1, k - 1, r, nums);
            } else {
                r.push_back(nums);
            }
        }
    }
 
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> r;
        vector<int> nums(k);
        combine(n, k, r, nums);
        return r;
    }
};

class Solution {
public:
    void combine(int n, int k, vector<vector<int>> &r, vector<int> &nums) {
        for (int i = n; i >= k; --i) {
            nums[k - 1] = i;
            if (k > 1) {
                combine(i - 1, k - 1, r, nums);
            } else {
                r.push_back(nums);
            }
        }
    }

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

The combinations doe not care about the order of the elements. For example, if we pick 3 numbers from 1 to 5, and if we sort the output, the last element (largest) could only be from 3 to 5, which are

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

If we put the last element, we can recursively put the second to last element, which is (n-1, k-1).

Iterative

Let’s emulate the process like this (pick 2 out of 3):

0 0  #initialization
1 0  i = 0
1 1  i = 1
1 2  candidate
1 3  candidate
2 2
2 3  candidate
3 3

The code that describes the backtracking process:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        int i = 0;
        vector<int> p(k, 0);
        while (i >= 0) {
            p[i]++;
            if (p[i] > n) {
                i --; // rewind  to previous number
            } else if (i == k - 1) {
                result.push_back(p);
            } else {
                i ++; // next number is no less
                p[i] = p[i - 1];
            }
        }
        return result;
    }
};

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        int i = 0;
        vector<int> p(k, 0);
        while (i >= 0) {
            p[i]++;
            if (p[i] > n) {
                i --; // rewind  to previous number
            } else if (i == k - 1) {
                result.push_back(p);
            } else {
                i ++; // next number is no less
                p[i] = p[i - 1];
            }
        }
        return result;
    }
};

Each iteration, increments the number at current position. If it is bigger than n, rewind to previous number. If we are dealing the k-th position, push the result. Otherwise advance to the next position and start from the same value so the combination result is unique and in non-descending order.

This is a DFS (Depth First Search).

Another way to obtain the combination is via the bitmasking algorithm: Using Bitmasking Algorithm to Compute the Combinations of an Array

–EOF (The Ultimate Computing & Technology Blog) —