Friday, October 10, 2014

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

void dfs(vector<vector<int> >& ret, int n, int k, int m, vector<int>& nums)
{
 if (nums.size() == k)
 {
  ret.push_back(nums);
 }
 else
 {
  for (int i = m; i <= n; i++)
  {
   nums.push_back(i);
   dfs(ret, n, k, i + 1, nums);
   nums.pop_back();
  }
 }
}

vector<vector<int> > combine(int n, int k) {
 vector<vector<int> > ret;
 vector<int> nums;
 dfs(ret, n, k, 1, nums);

 return ret;
}

No comments:

Post a Comment