# My solutions for using recursion and DP

• ``````/* recurisve solution*/
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
for(int i = 1; i <= n-k+1; i++)
{
ArrayList<Integer> path = new ArrayList<Integer>();
helper(path, k-1, n, res);
}
return res;
}

public void helper(List<Integer> line, int cnt, int n, List<List<Integer>> res)
{
if(cnt == 0)
{
return;
}
int last = line.get(line.size()-1);
for (int i = last+1; i <= n-cnt+1; i++)
{
ArrayList<Integer> path = new ArrayList<Integer>();
helper(path, cnt-1, n, res);
}
}

/*dp solution*/
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
// initialize
for (int i = 1; i <= n-k+1; i++)
{
List<Integer> line = new ArrayList<Integer>();
}

// from (n-1, m-1) ==> (n, m)
for (int i = 1; i < k; i++)
{
int j = 0;
int length = res.size();
while(j < length)
{
List<Integer> l = res.get(j);
int last = l.get(l.size()-1);
boolean firstRun = true;
for (int m = last + 1; m <= n- (k-i)+1; m++)
{
//change l and spawn new elements
if(firstRun)
{
firstRun = false;
}
else
{
List<Integer> newspawn = new ArrayList<Integer>();