Combinations

描述

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:

  1. [
  2.   [2,4],
  3.   [3,4],
  4.   [2,3],
  5.   [1,2],
  6.   [1,3],
  7.   [1,4],
  8. ]

递归

  1. // Combinations
  2. // 深搜，递归
  3. // 时间复杂度O(n!)，空间复杂度O(n)
  4. public class Solution {
  5.     public List<List<Integer>> combine(int n, int k) {
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         List<Integer> path = new ArrayList<>();
  8.         dfs(n, k, 1, 0, path, result);
  9.         return result;
  10.     }
  11.     // start，开始的数, cur，已经选择的数目
  12.     private static void dfs(int n, int k, int start, int cur,
  13.                             List<Integer> path, List<List<Integer>> result) {
  14.         if (cur == k) {
  15.             result.add(new ArrayList<>(path));
  16.         }
  17.         for (int i = start; i <= n; ++i) {
  18.             path.add(i);
  19.             dfs(n, k, i + 1, cur + 1, path, result);
  20.             path.remove(path.size() - 1);
  21.         }
  22.     }
  23. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/brute-force/combinations.html