Combinations
求n和k的组合数. 这个利用dfs就能找到左右组合的数字.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class Solution { public ArrayList<List<Integer>> combine(int n, int k) { ArrayList<List<Integer>> res = new ArrayList<List<Integer>>(); ArrayList<Integer> tmp = new ArrayList<Integer>(); dfs(res, tmp, k, n, 1);//start with 1, 1..n return res; } public void dfs(ArrayList<List<Integer>> res, List<Integer> tmp, int k, int n, int pos) { if(tmp.size() == k){ res.add(new ArrayList<Integer>(tmp)); return; } for(int i = pos; i <= n; i++) { tmp.add(i); dfs(res, tmp,k,n,i+1); tmp.remove(tmp.size()-1); } } } |