Given two integers

*n*and*k*, return all possible combinations of*k*numbers out of 1 ...*n*.
For example,

If

If

*n*= 4 and*k*= 2, a solution is:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

**Understand the problem:**

A classic permutation and combination problem. So using the recursion is a natural way.

**Solution:**

public class Solution { public ArrayList<ArrayList<Integer>> combine(int n, int k) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (n <= 0 || k <= 0 || n < k) { return result; } int[] num = new int[n]; for (int i = 0; i < n; i++) { num[i] = i + 1; } ArrayList<Integer> curr = new ArrayList<Integer>(); combineHelper(num, 0, 0, k, result, curr); return result; } private void combineHelper(int[] num, int start, int m, int k, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> curr) { if (m == k) { result.add(new ArrayList<Integer>(curr)); return; } for (int i = start; i < num.length; i++) { curr.add(num[i]); combineHelper(num, i + 1, m + 1, k, result, curr); curr.remove(curr.size() - 1); } } }

**Update on 9/25/15:**

public class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (n <= 0 || k <= 0 || n < k) { return result; } List<Integer> curr = new ArrayList<>(); combineHelper(1, n, 0, k, curr, result); return result; } private void combineHelper(int start, int n, int num, int k, List<Integer> curr, List<List<Integer>> result) { if (num == k) { result.add(new ArrayList<Integer>(curr)); return; } for (int i = start; i <= n; i++) { curr.add(i); combineHelper(i + 1, n, num + 1, k, curr, result); curr.remove(curr.size() - 1); } } }

## No comments:

## Post a Comment