## All posssible k combinations of numbers out of 1 to n (Combinations)

Given two integers $n$ and $k$, return all possible combinations of $k$ numbers out of $1 \dots n$.
INPUT: $n = 4, k = 2$
OUTPUT: [[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

Thoughts:
Using recursion and backtracking. We keep adding elements recursively until the size of partial solution exceeds $k$.

Code (C++):

```class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<int> partial;
vector<vector<int> > sol;
combineRecursion(n, k, partial, sol);
return sol;
}

void combineRecursion(int n, int k, vector<int> partial,
vector<vector<int> >& sol) {
if(partial.size() == k) {
if(find(sol.begin(), sol.end(), partial) == sol.end()) {
sort(partial.begin(), partial.end());
sol.push_back(partial);
}
} else if(partial.size() > k) {
return;
} else {
for(int i = n; i >= 1; --i) {
vector<int> partial_sol(partial);
partial_sol.push_back(i);
combineRecursion(i-1, k, partial_sol, sol);
}
}
}
};

Code (Java):
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
ArrayList<ArrayList<Integer>> sol = new ArrayList<ArrayList<Integer>>();
recursion(n,k,new ArrayList<Integer>(), sol);
return sol;
}

private void recursion(int n, int k, ArrayList<Integer> partial,
ArrayList<ArrayList<Integer>> sol) {
if(partial.size() == k && !sol.contains(partial)) {
Collections.sort(partial);
} else if(partial.size() > k) {
return;
} else {
for(int i = n; i >= 1; --i) {
ArrayList<Integer> partial_sol = new ArrayList<Integer>();
recursion(i-1, k, partial_sol, sol);
}
}
}
}

__ATA.cmd.push(function() {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});