AllCombinationsOfSizeK [全组合]

# 介绍

在组合数学，一个集的元素的组合是一个子集。S 的一个 k - 组合是 S 的一个有 k 个元素的子集。若两个子集的元素完全相同并顺序相异，它仍视为同一个组合，这是组合和排列不同之处。

# 回溯法

回溯法（英语：backtracking）是暴力搜寻法中的一种。

对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。

在经典的教科书中，八皇后问题展示了回溯法的用例。（八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布，使得没有一个皇后能攻击到另外一个。）

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现，现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

找到一个可能存在的正确的答案
在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

尝试错误法

尝试错误法，又称试误法（英语：trial and error），简称试错，是用来解决问题、获取知识的常见方法。此种方法可以视为简易解决问题的方法中的一种，与使用洞察力／直觉或理论推理的方法正好相反。

# 实现

# JavaScript

/*
  Problem: Given two numbers, n and k, make all unique combinations of k numbers from 1 to n and in sorted order

  What is combinations?
  - Combinations is selecting items from a collections without considering order of selection

  Example:
  - We have an apple, a banana, and a jackfruit
  - We have three objects, and need to choose two items, then combinations will be

  1. Apple & Banana
  2. Apple & Jackfruit
  3. Banana & Jackfruit

  To read more about combinations, you can visit the following link:
  - https://betterexplained.com/articles/easy-permutations-and-combinations/

  Solution:
  - We will be using backtracking to solve this questions
  - Take one element, and make all them combinations for k-1 elements
  - Once we get all combinations of that element, pop it and do same for next element
*/

class Combinations {
  constructor (n, k) {
    this.n = n
    this.k = k
    this.current = [] // will be used for storing current combination
    this.combinations = []
  }

  findCombinations (high = this.n, total = this.k, low = 1) {
    if (total === 0) {
      this.combinations.push([...this.current])
      return this.combinations
    }
    for (let i = low; i <= high; i++) {
      this.current.push(i)
      this.findCombinations(high, total - 1, i + 1)
      this.current.pop()
    }
    return this.combinations
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 扩展

注意组合与排列的区别，参考：

# 参考

编辑

上次更新: 2022/10/22, 22:03:41

← SetBit [位操作] GeneratePermutations [排列]→