原题传送门

1. 题目描述

2. Solution

1、思路分析
递归，回溯法。递归调用树如下图所示

2、代码实现

package Q0099.Q0077Combinations;  import java.util.ArrayList; import java.util.List;  /*     Solution 1: Backtracking  */ public class Solution {     public List<List<Integer>> combine(int n, int k) {         List<List<Integer>> result = new ArrayList<>();         combine(result, new ArrayList<>(), 1, n, k);         return result;     }      private void combine(List<List<Integer>> result, List<Integer> curResult, int start, int n, int k) {         if (k == 0) {             result.add(new ArrayList<>(curResult));             return;         }         for (int i = start; i <= n - k + 1; i++) {             curResult.add(i);             combine(result, curResult, i + 1, n, k - 1);             curResult.remove(curResult.size() - 1);         }     } } 

3、复杂度分析
时间复杂度: O(k \(C_n^k\))
空间复杂度: O(n)

3. Solution 2

1、思路分析
使用公式: C(n, k) = C(n-1, k-1) + C(n-1, k)
2、代码实现

/*     Solution 2: A short recursive solution based on C(n, k) = C(n-1, k-1) + C(n-1, k)  */ public class Solution2 {     public List<List<Integer>> combine(int n, int k) {         if (k == n || k == 0) {             List<Integer> row = new LinkedList<>();             for (int i = 1; i <= k; i++) row.add(i);             return new LinkedList<>(Collections.singletonList(row));         }         List<List<Integer>> result = combine(n - 1, k - 1);         result.forEach(e -> e.add(n));         result.addAll(combine(n - 1, k));         return result;     } } 

3、复杂度分析
时间复杂度: : )
空间复杂度: : )

4. Solution 3

1、思路分析
迭代。用一个长度为k的数组保存当前生成的组合序列，具体操作见下图

2、代码实现

package Q0099.Q0077Combinations;  import org.junit.Test;  import java.util.ArrayList; import java.util.List;  /*     Iteration  */ public class Solution3 {     public List<List<Integer>> combine(int n, int k) {         List<List<Integer>> result = new ArrayList<>();         int i = 0;         int[] nums = new int[k];         while (i >= 0) {             nums[i]++;      // 当前数字加1             if (nums[i] > n) --i; // 当前数字大于n，对应回溯法的 start = n + 1，返回上一层             else if (i == k - 1) {  // 数字个数够了                 List<Integer> curResult = new ArrayList<>();                 for (int num : nums) curResult.add(num);                 result.add(curResult);             } else {    // 进入更新下一个数字                 ++i;                 nums[i] = nums[i - 1]; // 把下一个数字置为上一个数字             }         }         return result;     } } 

3、复杂度分析
时间复杂度: : )
空间复杂度: : )