# 排列组合

## Index

* [排列](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#排列)
  * [下一个排列](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#下一个排列)
  * [上一个排列](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#上一个排列)
  * [STL 提供的实现（下一个排列、上一个排列） TODO](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#stl-提供的实现下一个排列上一个排列-todo)
  * [第 k 个排列](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#第-k-个排列)
  * [全排列（无重复）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#全排列无重复)
    * [基于插入的写法](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#基于插入的写法)
    * [基于交换的写法](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#基于交换的写法)
  * [全排列（有重复）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#全排列有重复)
    * [基于插入的写法](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#基于插入的写法-1)
    * [基于交换的写法](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#基于交换的写法-1)
  * [【注】全排序的时间复杂度](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#注全排序的时间复杂度)
* [组合](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#组合)
  * [组合（n 选 k，无重复）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#组合n-选-k无重复)
  * [组合（n 选 k，有重复）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#组合n-选-k有重复)
  * [组合总和（数字不重复但可重复使用）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#组合总和数字不重复但可重复使用)
  * [组合总和 2（存在重复数字但每个数字只能使用一次）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#组合总和-2存在重复数字但每个数字只能使用一次)
  * [组合总和 3（数字不重复且指定数量）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#组合总和-3数字不重复且指定数量)
* [【说明】](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#说明)
  * [字典序](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#字典序)
  * [关于 `for(i=0;..)` 与 `for(i=step;..)` 的说明](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#关于-fori0-与-foristep-的说明)
  * [【注】关于 `dfs(step+1)`、`dfs(i+1)`、`dfs(i)` 的说明](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#注关于-dfsstep1dfsi1dfsi-的说明)
    * [`dfs(step+1)` 和 `dfs(i+1)`](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#dfsstep1-和-dfsi1)
    * [`dfs(i+1)` 和 `dfs(i)`](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#dfsi1-和-dfsi)

## 排列

### 下一个排列

> LeetCode - [31. 下一个排列](https://leetcode-cn.com/problems/next-permutation/description/)

**题目描述**

```
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
```

**思路**

* **相邻的两个排列有最长公共前缀**，然后找到需要交换的**高位**和**低位**
* 根据字典序的定义，依照如下步骤寻找下一个排列

  > [字典序](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#字典序)
* 从后往前找需要改变的**高位** hi，即**第一个降序**元素的位置

  ```
  1 5 8 4 7 6 5 3 1
        ↑
        hi
  ```
* 从后往前找需要交换的**低位** lo，即**第一个大于** nums\[hi] 的位置

  ```
  1 5 8 4 7 6 5 3 1
        ↑     ↑
        hi    lo
  ```
* 交换 nums\[lo] 与 nums\[hi]

  ```
  1 5 8 4 7 6 5 3 1
        ↓     ↓
  1 5 8 5 7 6 4 3 1
        ↑     ↑
        hi    lo     (hi 位置不变)
  ```
* **反转** hi 之后的序列，即 nums\[hi+1: n)

  ```
  1 5 8 5 7 6 4 3 1
          ↓ ↓ ↓ ↓ ↓
  1 5 8 5 1 3 4 6 7
        ↑     ↑
        hi    lo     (hi 位置不变)
  ```

  **C++**

  ```cpp
  class Solution {
  public:
   void nextPermutation(vector<int>& nums) {
       int n = nums.size();
       if (n <= 1) return;

       int hi = n - 2;
       // 1. 从后往前找需要改变的**高位** hi，即第一个降序元素的位置
       while (hi >= 0 && nums[hi + 1] <= nums[hi])
           hi--;

       if (hi >= 0) {
           // 2. 从后往前找需要交换的**低位** lo，即第一个大于 nums[hi] 的位置
           int lo = n - 1;
           while (lo >= 0 && nums[lo] <= nums[hi])
               lo--;
           // 3. 交换 nums[lo] 与 nums[hi]
           swap(nums[hi], nums[lo]);
       }

       // 4. 反转 hi 之后的序列，即 nums[hi+1: n)
       reverse(nums.begin() + hi + 1, nums.end());
       // 当 i == -1 时，该操作会使序列从字典序最大转为最小，这与 STL 中提供的 next_permutation 略有不同
   }
  };
  ```

### 上一个排列

> LintCode - [51. 上一个排列](https://www.lintcode.com/problem/previous-permutation/description)

**问题描述**

```
给定一个整数数组来表示排列，找出其上一个排列。
排列中可能包含重复的整数

样例
给出排列[1,3,2,3]，其上一个排列是[1,2,3,3]

给出排列[1,2,3,4]，其上一个排列是[4,3,2,1]
```

**思路**

* 实际上就是[下一个排列](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#下一个排列)的逆过程
* 从右往左找**第一个升序**的位置 hi
* 从右往左找**第一个小于** nums\[hi] 的位置 lo
* 交换 nums\[lo] 和 nums\[hi]
* 反转 hi 之后的位置

**C++**

```cpp
class Solution {
public:
    /*
    * @param nums: A list of integers
    * @return: A list of integers that's previous permuation
    */
    vector<int> previousPermuation(vector<int> &nums) {
        int n = nums.size();

        if (n <= 1) return nums;

        int hi = n - 2;
        // 1. 从右往左找**第一个升序**的位置 hi
        while (hi >= 0 && nums[hi] <= nums[hi + 1])
            hi--;

        if (hi >= 0) {
            int lo = n - 1;
            // 2. 从右往左找**第一个小于** nums[hi] 的位置 lo
            while (lo >= 0 && nums[lo] >= nums[hi])
                lo--;
            // 3. 交换 nums[lo] 和 nums[hi]
            swap(nums[lo], nums[hi]);
        }

        // 4. 反转 hi 之后的位置
        reverse(nums.begin() + hi + 1, nums.end());

        return nums;  // 注意这里要你返回一个值
    }
};
```

### STL 提供的实现（下一个排列、上一个排列） TODO

* STL 提供了两个函数用于生成排列

  ```cpp
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);

  bool prev_permutation (BidirectionalIterator first,
                         BidirectionalIterator last );
  ```
* 这两个函数均以**字典序**比较函数 `lexicographical_compare()`为基础生成下一个或上一个排列
* 因此在使用这两个函数前，需要先对原序列进行**排序**

**C++**

```cpp
```

### 第 k 个排列

> LeetCode - [60. 第k个排列](https://leetcode-cn.com/problems/permutation-sequence/description/)

**问题描述**

```c
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"

给定 n 和 k，返回第 k 个排列。

说明：
  给定 n 的范围是 [1, 9]。
  给定 k 的范围是 [1, n!]。
示例 1:
  输入: n = 3, k = 3
  输出: "213"
示例 2:
  输入: n = 4, k = 9
  输出: "2314"
```

**思路**

* 因为字典序的性质，实际不需要求出前 k-1 个序列
* 整体思路有点像**桶排序**
* 以 `{1 2 3 4 5}` 为例，找出其中第 `14` 个序列

  ```
  首先，可以先按第一个位置的元素，把所有序列依次到对应的桶中
  在开始之前，先 k--，因为计算机计数是从 0 开始的，此时 k=13（下面会说明为什么需要减 1）
  第 1 轮：剩余 5 个元素，有 5 个桶
    第0个桶：以 1 开头，剩余元素 {2 3 4 5} 
    第1个桶：以 2 开头，剩余元素 {1 3 4 5} 
    第2个桶：以 3 开头，剩余元素 {1 2 4 5} 
    第3个桶：以 4 开头，剩余元素 {1 2 3 5}
    第4个桶：以 5 开头，剩余元素 {1 2 3 4}
  每个桶中有 4!=24 个序列，因为是有序的，显然第 k=13 个元素必然在第 `13/(4!) = 0` 个桶中
    换言之，第 14 个元素必然以 1 开头
  移除序列中的 1，剩余序列变为 {2 3 4 5}，k = 13 % 24 = 13

  第 2 轮：剩余 4 个元素，有 4 个桶
    第0个桶：以 2 开头，剩余元素 {3 4 5} 
    第1个桶：以 3 开头，剩余元素 {2 4 5} 
    第2个桶：以 4 开头，剩余元素 {2 3 5} 
    第3个桶：以 5 开头，剩余元素 {2 3 4}
  每个桶中有 3!=6 个元素。显然，第 k=13 个元素应该在第 `13/(3!) = 2` 个桶中
    即第 14 个元素的前缀为 14
  移除序列中的 4，剩余序列变为 {2 3 5}，k = 13 % 6 = 1

  第 3 轮：剩余 3 个元素，有 3 个桶
    第0个桶：以 2 开头，剩余元素 {3 5} 
    第1个桶：以 3 开头，剩余元素 {2 5} 
    第2个桶：以 5 开头，剩余元素 {3 5} 
  此时每个桶中有 2!=2 个元素。第 k=1 个元素应该在第 `1/(2!)=0` 个桶中（如果开始时 k 不减 1，这里就会出现问题）
    即第 14 个元素的前缀为 142
  移除序列中的 2，剩余序列变为 {3 5}，k = 1 % 2 = 1

  第 4 轮：剩余 2 个元素，有 2 个桶
    第0个桶：以 3 开头，剩余元素 {5} 
    第1个桶：以 5 开头，剩余元素 {3} 
  此时每个桶中有 1!=1 个元素。第 k=1 个元素应该在第 `1/(1!)=1` 个桶中
    即第 14 个元素的前缀为 1425
  移除序列中的 5，剩余序列变为 {3}，k = 1 % 1 = 0

  第 5 轮：剩余 1 个元素，有 1 个桶
    第0个桶：以 3 开头，无剩余元素
  此时每个桶中有 0!=1 个元素（实际上此时桶中没有元素）。
  第 k=0 个元素应该在第 `0/(0!)=0` 个桶中（最后一轮利用 0!=1 的性质不需要特别处理）
    即第 14 个元素为 14253
  ```

**C++**

```cpp
class Solution {
public:
    string getPermutation(int n, int k) {

        // nums: {1, 2, 3, ..., n}
        // 换成其他字符，按字典序存放到对应位置即可
        vector<int> nums(n + 1, 0);
        for (int i = 0; i < n; i++) // 注意：桶的下标是从 0 开始的
            nums[i] = i + 1;

        // dp: {0!=1, 1!, 2!, ..., n!}
        vector<int> dp(n + 1, 1);  // 根据上面的推导，dp[0]=1 正好可以处理最后一轮
        for (int i = 1; i <= n; i++)
            dp[i] = dp[i - 1] * i;

        k--;
        stringstream ss;
        for (int i = 1; i <= n; i++) {  // 从 1 开始
            int index = k / dp[n - i];  // 实际上没有用到 dp[n] = n!
            ss << nums[index];
            nums.erase(nums.begin() + index);  // 注意，每轮删除已处理的元素
            k = k % dp[n - i];
        }

        return ss.str();
    }
};
```

### 全排列（无重复）

> LeetCode [46. 全排列](https://leetcode-cn.com/problems/permutations/description/)

**题目描述**

```
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
```

**思路 1**

* 利用下一个排列，先对数组排序，然后不断生成下一个排列

**思路 2**

* **深度优先搜索**
* 易知，当序列中的元素不重复时，存在 `n!` 种不同的排列；
* 考虑第一个位置，有 n 种可能
* 当选定了第一个位置，第二个位置有 n-1 种可能
* 因为**每次搜索的状态数**是递减的，所以这里的 dfs 是一个**循环递归**的过程

#### 基于插入的写法

* 代码量多一点，但比较好理解

  \`\`\`C++ class Solution { vector > ret; vector tmp; vector used; int n = 0;

  void dfs(vector& nums, int step) { if (tmp.size() == n) { ret.push\_back(tmp); return; }

  ```
    for (int i = 0; i < n; i++) {   // i 每次从 0 开始，因为元素可以重复使用
        if (used[i]) continue;      // 但是在每一轮中，如果用过了需要跳过
                                    // 每一轮指的是生成一次排列的过程
        used[i] = 1;            // 标记使用
        tmp.push_back(nums[i]);
        dfs(nums, step + 1);
        tmp.pop_back();         // 回溯
        used[i] = 0;
    }
  ```

  }

public: vector > permute(vector& nums) { n = nums.size(); used.resize(n, 0);

```
    dfs(nums, 0);
    return ret;
}
```

};

````
> [【注】关于 `for(i=0;..)` 与 `for(i=step;..)` 的说明](#注关于-fori0-与-foristep-的说明)

#### 基于交换的写法
- 基于交换的写法，代码比较简洁，但个人认为有一点不好理解
```C++
class Solution {
    vector<vector<int> > ret;

    //void dfs(vector<int> nums, int step) {  // 值传递
    void dfs(vector<int>& nums, int step) {   // 引用传递
        if (step >= nums.size()) {
            ret.push_back(nums);
            return;
        }

        for (int i = step; i < nums.size(); i++) { // 注意：这里 i 从 step 开始
            swap(nums[step], nums[i]);
            dfs(nums, step + 1);
            swap(nums[step], nums[i]);  // 如果 nums 是值传入，则不需要这步；否则不能省略
        }
    }

public:
    vector<vector<int> > permute(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }
};
````

### 全排列（有重复）

> LeetCode - [47. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/description/)

**题目描述**

```
给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
```

**思路 1**

* 使用无重复时的方法，用 set 剔除重复（不推荐）

**思路 2**

* 先对原序列**排序**，使相同的元素相邻；此时**只处理第一个相同元素**，其余跳过；

#### 基于插入的写法

```cpp
class Solution {
    vector<vector<int> > ret;
    vector<int> tmp;
    vector<bool> used;
    int n = 0;

    void dfs(vector<int>& nums, int step) {
        if (tmp.size() == n) {
            ret.push_back(tmp);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))
                continue;  // 这里的 !used[i - 1] 稍难理解，可以配合 IDE 或者手推一下整个过程

            used[i] = 1;
            tmp.push_back(nums[i]);
            dfs(nums, step + 1);
            tmp.pop_back();
            used[i] = 0;
        }
    }

public:
    vector<vector<int> > permuteUnique(vector<int>& nums) {
        n = nums.size();
        used.resize(n, 0);
        sort(nums.begin(), nums.end());

        dfs(nums, 0);
        return ret;
    }
};
```

#### 基于交换的写法

```cpp
class Solution {
    vector<vector<int> > ret;

    //void dfs(vector<int>& nums, int step) { // 传引用无法得出正确结果
    void dfs(vector<int> nums, int step) {    // 注意这里应该使用**值传递**
        int n = nums.size();
        if (step >= n - 1) {
            ret.push_back(nums);
            return;
        }

        for (int i = step; i < n; i++) {
            if (i != step && nums[i] == nums[step])
                continue;

            swap(nums[i], nums[step]);
            dfs(nums, step + 1);
            //swap(nums[i], nums[step]); // 传引用配合回溯无法得出正确结果，
                                         // 原因在于此时会破坏剩余数组的有序性
        }
    }
public:
    vector<vector<int> > permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);

        return ret;
    }
};
```

### 【注】全排序的时间复杂度

* 不重复情况下，n 个元素的不同全排列为 `n!` 个，所以算法的时间复杂度至少为 `O(N!)`
* 因此，全排列算法对大型的数据是无法处理的

## 组合

### 组合（n 选 k，无重复）

> LeetCode - [77. 组合](https://leetcode-cn.com/problems/combinations/description/)

**问题描述**

```c
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
  [
    [2,4],
    [3,4],
    [2,3],
    [1,2],
    [1,3],
    [1,4],
  ]
```

**思路**

* 带**回溯**的深度优先搜索，类似[全排列（无重复）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#全排列无重复)

**C++**

```cpp
class Solution {
    vector<vector<int> > ret;
    vector<int> tmp;   // 保存中间结果
    int K;

    void dfs(vector<int>& nums, int step) {
        if (tmp.size() >= K) {
            ret.push_back(tmp);
            return;
        }

        for (int i = step; i < nums.size(); i++) {
            tmp.push_back(nums[i]);  // nums[i] == i，所以这里直接 push(i) 也可以
            dfs(nums, i + 1);
            tmp.pop_back();
        }
    }

public:
    vector<vector<int> > combine(int n, int k) {

        K = k;
        vector<int> nums;
        for (int i = 0; i < n; i++)
            nums.push_back(i + 1);

        dfs(nums, 0);
        return ret;
    }
};
```

### 组合（n 选 k，有重复）

（未验证）

* 如果要求每个组合中不重复，则可以先去重，再按照无重复的做法
* 如果不要求去重，则直接按照无重复的做法即可

### 组合总和（数字不重复但可重复使用）

> LeetCode - [39. 组合总和](https://leetcode-cn.com/problems/combination-sum/description/)

**思路**

* 深度优先搜索
* 关键在于每个数字可以重复使用

**C++**

```cpp
class Solution {
    vector<vector<int> > ret;
    vector<int> tmp;
    int cur = 0;
    int target = 0;

    void dfs(vector<int>& nums, int step) {
        if (cur >= target) {
            if (cur == target)
                ret.push_back(tmp);
            return;
        }

        for (int i = step; i < nums.size(); i++) {
            cur += nums[i];
            tmp.push_back(nums[i]);
            dfs(nums, i);  // 因为每个数组可以重复使用，所以是 dfs(i) 而不是 dfs(i+1)
            cur -= nums[i];
            tmp.pop_back();
        }
    }

public:
    vector<vector<int> > combinationSum(vector<int>& candidates, int target) {
        this->target = target;

        //sort(candidates.begin(), candidates.end()); // 不需要
        dfs(candidates, 0);

        return ret;
    }
};
```

> [【注】关于 `dfs(step+1)`、`dfs(i+1)`、`dfs(i)` 的说明](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#注关于-dfsstep1dfsi1dfsi-的说明)

### 组合总和 2（存在重复数字但每个数字只能使用一次）

> LeetCode - [40. 组合总和 II](https://leetcode-cn.com/problems/combination-sum-ii/description/)

**思路**

* DFS，关键是如何去除重复情况

**C++**

```cpp
class Solution {
    vector<vector<int> > ret;
    vector<int> tmp;
    int cur = 0;
    int target;

    void dfs(vector<int>& nums, int step) {
        if (cur >= target) {
            if (cur == target)
                ret.push_back(tmp);
            return;
        }

        for (int i = step; i < nums.size(); i++) {
            if (i > step && nums[i] == nums[i - 1]) // 代码说明 1
                continue;

            cur += nums[i];
            tmp.push_back(nums[i]);
            dfs(nums, i + 1);       // i+1 而不是 i，因为不能重复使用
            tmp.pop_back();
            cur -= nums[i];
        }
    }
public:
    vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
        this->target = target;

        sort(candidates.begin(), candidates.end());  // 因为存在重复，需要先排序
        dfs(candidates, 0);

        return ret;
    }
};
```

**代码说明 1**

```
if (i > step && nums[i] == nums[i - 1])
```

* 以 ![](/files/-L_7DUX8hTCyy-tyLMNx) 为例
* 这段代码实际上并不会过滤 ![](/files/-L_7DUXBa6rzJCwS0v7O) ——`i == step` 的情况
* 真正重复的情况是 ![](/files/-L_7DUXEdsdR3kcy4XBR) 和 ![](/files/-L_7DUXGdlCxziVUwRae)，而这段代码的目的是过滤 ![](/files/-L_7DUXLKDB5jAZpj0LS) ——`i > step` 的情况

### 组合总和 3（数字不重复且指定数量）

> LeetCode - [216. 组合总和 III](https://leetcode-cn.com/problems/combination-sum-iii/description/)

**问题描述**

```c
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
```

**思路**

* 在[组合总和（数字不重复但可重复使用）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#组合总和数字不重复但可重复使用)上稍作修改即可

**C++**

```cpp
class Solution {
    vector<vector<int> > ret;
    vector<int> tmp;
    int cur = 0;
    int K;

    void dfs(int n, int step) {
        if (cur >= n) {
            if (cur == n && tmp.size() == K)  // 同时满足才加入结果集
                ret.push_back(tmp);
            return;
        }

        for (int i = step; i <= 9; i++) {

            cur += i;
            tmp.push_back(i);
            dfs(n, i + 1);    // 因为数字不能重复使用，所以是 dfs(i+1)
            tmp.pop_back();
            cur -= i;
        }
    }

public:
    vector<vector<int> > combinationSum3(int k, int n) {
        K = k;

        dfs(n, 1);
        return ret;
    }
};
```

## 【说明】

### 字典序

* 在处理排列问题时，通常时根据**字典序**来生成下一个排列
* 在字典序中，记序列的**升序**为第一个排列，**降序**为最后一个排列

**高位与低位**

* 对序列中任意两个位置而言，靠近左侧的为**高位**，靠近右侧的为低位
* 生成排列的过程就是不断增大**高位**，减小**低位**的过程

  ```
  1 2 3
  1 3 2
  2 1 3
  2 3 1
  3 1 2
  3 2 1
  ```

### 关于 `for(i=0;..)` 与 `for(i=step;..)` 的说明

* `for(i=0;..)` 需配合 `used` 标记使用
  * [全排列（无重复，基于插入的写法）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#基于插入的写法)
  * [全排列（有重复，基于插入的写法）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#基于插入的写法-1)
* `for(i=step;..)`
  * 所有组合问题
* 简单来说，以 `{1 2 3 4}` 为例
  * `for(i=0;..)` 用于以下情况

    ```
    1 + {2 3 4}
    2 + {1 3 4}
    ...
    ```

    * used 用于标记开头的 `1`、`2`等
  * `for(i=step;..)` 用于以下情况

    ```
    1 + {2 3 4}
    2 + {3 4}
    ...
    ```

    * 一般不需要 `used` 标记

### 【注】关于 `dfs(step+1)`、`dfs(i+1)`、`dfs(i)` 的说明

（以下均为个人小结，并没有严格验证）

#### `dfs(step+1)` 和 `dfs(i+1)`

* 简单来说，`dfs(step+1)` 指的是生成 `tmp` 序列中的第 `step+1` 个位置；`dfs(i+1)` 指的是使用 `nums` 中的第 `i+1` 个元素
  * 在[排列（无重复）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#全排列无重复)问题中，使用的是 `dfs(step+1)`
  * 在[组合（无重复）](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#组合n-选-k无重复)问题中，使用的是 `dfs(i+1)`
  * 相关代码段

    ```cpp
    // 排列
    for (int i = step; i < nums.size(); i++) {
        // ...
        dfs(nums, step + 1);
        // ...
    }

    // 组合
    for (int i = step; i < nums.size(); i++) {
        // ...
        dfs(nums, i + 1);
        // ...
    }
    ```
* 以不重复集合 `{1 2 3 4}` 为例说明：
  * 排列问题中用过的元素还可能被再次使用；

    ```
    step = 0 时，即第一个位置是 1
      所有的排列为 1 + {2 3 4} 
    step = 1 时，即第一个位置是 2
      所有的排列为 2 + {1 3 4}    # 1 又出现在了后序元素中
    ...
    ```
  * 而组合问题中使用过的元素，之后不再使用

    ```
    step = 0 时，即第一个位置是 1
      所有的组合为 1 + {2 3 4}
    step = 1 时，即第一个位置是 2
      所有的组合为 2 + {3 4}      # 1 不再使用了
    ```
  * 正是由于这个区别导致**排列**中应该使用 `dfs(step+1)`，而**组合**中应该使用 `dfs(i+1)`

#### `dfs(i+1)` 和 `dfs(i)`

* 在[组合总和](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xAuDU0HtA5dE_ZY#组合总和)问题中，还用到了 `dfs(i)`

  ```
  for (int i = step; i < nums.size(); i++) {
      // ...
      dfs(nums, i);
      // ...
  }
  ```

  * 一方面，它跟组合问题类似，用过的数字不再使用；因此使用的是 `i` 而不是 `step`
  * 另一方面，每个数字可以重复使用，因此使用的是 `dfs(i)` 而不是 `dfs(i+1)`


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/zhuan-ticpai-lie-zu-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.