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:
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]Solution:O(n)
public class Solution { public ArrayList<ArrayList<Integer>> combine(int n, int k) { ArrayList<ArrayList<Integer>> list = new ArrayList<>(); if(k > n || k <1) return list; if(k == 1){ for(int i=1; i<=n; i++){ ArrayList<Integer> slist = new ArrayList<>(); slist.add(i); list.add(slist); } }else{ ArrayList<ArrayList<Integer>> slist1 = combine(n-1, k-1); ArrayList<ArrayList<Integer>> slist2 = combine(n-1, k); for(int i=0; i<slist1.size();i++){ slist1.get(i).add(n); list.add(slist1.get(i)); } for(int i=0; i<slist2.size();i++){ list.add(slist2.get(i)); } } return list; } }
沒有留言:
張貼留言