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], ]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