# Java solution with backtracking

• ``````public class Solution {
List<List<Integer>> results = new ArrayList<List<Integer>>();
public List<List<Integer>> combine(int n, int k) {
findResult(1, n, k, new ArrayList<Integer>());
return results;
}

private void findResult(int start, int end, int k, List<Integer> combo){
if (k == 0){
List<Integer> result = new ArrayList<Integer>();
return;
}
int j = 1;
for (int i=start;i<=end;i++){
findResult(start+j, end, k-1, combo);
combo.remove(combo.size()-1);
j++;
}
}
}``````

• This solution takes more time. Below is the CPP version. :)

``````vector<vector<int>> ans;

void run_recursively(const vector<int> &_arr, const int start,
const int end, const int count)
{
if (0 == count) {
ans.push_back(_arr);
return;
}

for (int iii = start; iii <= end; iii++) {
vector<int> arr = _arr;
arr.push_back(iii);
run_recursively(arr, iii + 1, end, count - 1);
}
}

class Solution {
public:
vector<vector<int>> combine(int n, int k) {
ans.clear();
run_recursively(vector<int>(), 1, n, k);
return ans;
}
};``````

• Here is a more fast CPP version.

``````// Reference: https://leetcode.com/discuss/43968/java-solution-with-backtracking
void combine_backtrack_implement(vector<vector<int> > *_matrix, vector<int> *_nums,
const int start, const int end, const int index, const int k)
{
if (index == k) {
_matrix->push_back(*_nums);
return;
}

for (int iii = start; iii <= end - k + index + 1; iii++) {
(*_nums)[index] = iii;
combine_backtrack_implement(_matrix, _nums, iii + 1, end, index + 1, k);
}
}

class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int> > ans;

if (k > n || k <= 0)
return ans;

vector<int> nums(k, 0);
combine_backtrack_implement(&ans, &nums, 1, n, 0, k);
return ans;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.