神刀安全网

The Combinations in C/C++

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

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]
[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 canrecursively 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
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 process:

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).

–EOF–

GD Star Rating

loading…

415 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » The Combinations in C/C++

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址