Problem:
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], ]
Method:
Compare this one with the permutation problem, the differences are the following:
1) We don’t need to keep an array of used element, since combination does not care sequence.
2) But we do not iterate every element from 1 to n, instead, we iterate from the last element in ‘item’.
3) Very Important!!!! When adding to res, do remember to copy the element instead of just copy the reference.
Code:
public class Solution { public ArrayList<ArrayList<Integer>> combine(int n, int k) { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if (k <= 0 || n <= 0) return res; ArrayList<Integer> item = new ArrayList<Integer>(); return helper(n, k, item,res); } public ArrayList<ArrayList<Integer>> helper(int n, int left, ArrayList<Integer> item, ArrayList<ArrayList<Integer>> res){ if (left == 0){ res.add(new ArrayList<Integer>(item)); return res; } int i; if (item.size() == 0){ i = 1; }else{ i = item.get(item.size()-1) + 1; } for (; i <= n; i++){ item.add(i); helper(n, left-1, item, res); item.remove(item.size()-1); } return res; } }