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], ]
import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; public class Solution { public ArrayList<ArrayList<Integer>> combine(int n, int k) { // Start typing your Java solution below // DO NOT write main() function HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>(); ArrayList<Integer> tmp = new ArrayList<Integer>(); recursion(set,tmp,n,k); return new ArrayList<ArrayList<Integer>>(set); } public void recursion(HashSet<ArrayList<Integer>> set,ArrayList<Integer> tmp, int n, int k){ if(tmp.size() == k){ Collections.sort(tmp); set.add(tmp); } else if(tmp.size() > k){ return; } else{ for(int i = n; i>0 ; i--){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(tmp);//add existing number to arraylist temp.add(i); recursion(set,temp,i-1,k);//level -1 } } } }
===================================================================
public class Solution { public ArrayList<ArrayList<Integer>> combine(int n, int k) { // Start typing your Java solution below // DO NOT write main() function return dfs(n,k); } public ArrayList<ArrayList<Integer>> dfs(int n ,int k){ ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(k ==1){ for(int i = 1 ; i <= n ;i++){ ArrayList<Integer> sub = new ArrayList<Integer>(); sub.add(i); res.add(sub); } } else{ for(int i = n;i > 1; i--){ ArrayList<ArrayList<Integer>> comb = dfs(i-1,k-1); for(ArrayList<Integer> sub:comb){ sub.add(i); res.add(sub); } } } return res; } }
mistake：1）forgot to sort list 2)use new arraylist to add existing number 3) level -1
public class Solution { public ArrayList<ArrayList<Integer>> combine(int n, int k) { // Start typing your Java solution below // DO NOT write main() function ArrayList<Integer> col = new ArrayList<Integer>(); ArrayList<ArrayList<Integer>> re = new ArrayList<ArrayList<Integer>>(); getlist(n,k,col,re,0); return re; } public void getlist(int n, int k, ArrayList<Integer> col, ArrayList<ArrayList<Integer>> re, int start){ if(col.size()==k){ ArrayList<Integer> t = new ArrayList<Integer>(col); re.add(t); return; } for(int i=start; i<n; i++){ col.add(i+1); getlist(n,k,col,re,i+1); col.remove(col.size()-1); } } }