77. Combinations

Description

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

code

class Solution {
private:
void backtracking(vector<vector<int>> & res,vector<int> & temp,int * num,int start,int k,int n){
if(temp.size()==k){
res.push_back(temp);
return;
}
for(int i=start;i<n;++i){
temp.push_back(num[i]);
backtracking(res,temp,num,i+1,k,n);
temp.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> temp;
int * array=new int[n];
for(int i=1;i<=n;++i)
array[i-1]=i;
backtracking(res,temp,array,0,k,n);
delete array;
return res;
}
};

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;
else if (i == k - 1) result.push_back(p);
else {
++i;
p[i] = p[i - 1];
}
}
return result;
}
};

For example, the (4, 2) test case yields:

Incremented element at index 0
[1, 0]
Moved index to the right, and copied the value from the left
[1, 1]
Incremented element at index 1
[1, 2]
Combination found!
Incremented element at index 1
[1, 3]
Combination found!
Incremented element at index 1
[1, 4]
Combination found!
Incremented element at index 1
[1, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[2, 5]
Moved index to the right, and copied the value from the left
[2, 2]
Incremented element at index 1
[2, 3]
Combination found!
Incremented element at index 1
[2, 4]
Combination found!
Incremented element at index 1
[2, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[3, 5]
Moved index to the right, and copied the value from the left
[3, 3]
Incremented element at index 1
[3, 4]
Combination found!
Incremented element at index 1
[3, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[4, 5]
Moved index to the right, and copied the value from the left
[4, 4]
Incremented element at index 1
[4, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[5, 5]
n exceeded at 0, moving index to the left
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

学籍管理系统文档

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017