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], ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
publicclassSolution{ public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<>(); combination(result, new ArrayList<Integer>(), n, k, 1); return result; } publicvoidcombination(List<List<Integer>> result, ArrayList<Integer> cur, int n, int k, int start){ if (cur.size() == k) { result.add(new ArrayList<Integer>(cur)); } else { for (int i = start; i <= n; i++) { cur.add(i); combination(result, cur, n, k, i + 1); cur.remove(cur.size() - 1); } } } }
Another solution based on mathmetical properties
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
publicclassSolution{ public List<List<Integer>> combine(int n, int k) { // base case if (k == n || k == 0) { List<Integer> row = new LinkedList<>(); for (int i = 1; i <= k; ++i) { row.add(i); } returnnew LinkedList<>(Arrays.asList(row)); } List<List<Integer>> result = this.combine(n - 1, k - 1); // n is selected result.forEach(e -> e.add(n)); result.addAll(this.combine(n - 1, k)); // n is not selected return result; } }