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:

  1. [
  2.   [2,4],
  3.   [3,4],
  4.   [2,3],
  5.   [1,2],
  6.   [1,3],
  7.   [1,4],
  8. ]

递归

  1. // Combinations
  2. // 深搜，递归
  3. // 时间复杂度O(n!)，空间复杂度O(n)
  4. class Solution {
  5. public:
  6.     vector<vector<int> > combine(int n, int k) {
  7.         vector<vector<int> > result;
  8.         vector<int> path;
  9.         dfs(n, k, 1, 0, path, result);
  10.         return result;
  11.     }
  12. private:
  13.     // start，开始的数, cur，已经选择的数目
  14.     static void dfs(int n, int k, int start, int cur,
  15.             vector<int> &path, vector<vector<int> > &result) {
  16.         if (cur == k) {
  17.             result.push_back(path);
  18.         }
  19.         for (int i = start; i <= n; ++i) {
  20.             path.push_back(i);
  21.             dfs(n, k, i + 1, cur + 1, path, result);
  22.             path.pop_back();
  23.         }
  24.     }
  25. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/brute-force/combinations.html