专题-排列组合

2020-08-18 | 阅读：次

Index

排列
组合
【说明】

排列

下一个排列

LeetCode - 31. 下一个排列

题目描述

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

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

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

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

思路

相邻的两个排列有最长公共前缀，然后找到需要交换的高位和低位

根据字典序的定义，依照如下步骤寻找下一个排列

字典序
从后往前找需要改变的高位 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++

    void nextPermutation(vector<int>& nums) {
        int pos = nums.size()-1;
        while(pos > 0 && nums[pos] <= nums[pos-1])
            pos--;
        reverse(nums.begin()+pos, nums.end());
        if(pos > 0){
            auto it = upper_bound(nums.begin()+pos, nums.end(), nums[pos-1]);
            swap(*it, nums[pos-1]);
        }
    }

上一个排列

LintCode - 51. 上一个排列

问题描述

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

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

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

思路

实际上就是下一个排列的逆过程
1. 从右往左找第一个升序的位置 hi
2. 从右往左找第一个小于 nums[hi] 的位置 lo
3. 交换 nums[lo] 和 nums[hi]
4. 反转 hi 之后的位置

C++

    vector<int> previousPermuation(vector<int> &nums) {
        int l = nums.size() - 1, r = l - 1;
        // 1.从右往左找*第一个升序*位置r 
        while (r >= 0 && nums[r] <= nums[r + 1]) --r; 
       
        if (r >= 0) {
            // 2.找*第一个小于nums[l]位置l
            while (l >= 0 && nums[l] >= nums[r]) --l; 
            swap(nums[l], nums[r]);  // 3. 交换 nums[l] 和 nums[r]
        }
        reverse(nums.begin() + r + 1, nums.end());// 4. 反转 r 之后的位置
        return nums; 
    }
    //[1,3,2,4]，其上一个排列是[1,2,3,4]
    //r = 1   , 2
    //l = 2   , 3
    //swap(1,2,3,4)
    //reverse   1,2,4,3

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

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

bool next_permutation (BidirectionalIterator first,
                       BidirectionalIterator last);

bool prev_permutation (BidirectionalIterator first,
                       BidirectionalIterator last );

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

C++

第k个排列

LeetCode - 60. 第k个排列

问题描述

给出集合 [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++

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题目的精简代码

    string getPermutation(int n, int k) {
        string res, num = "123456789";
        int f[9]= {1,1,2,6,24,120,720, 720*7, 720*56};
        --k;
        for (int i = n; i >= 1; --i) {
            int j = k / f[i - 1];
            k %= f[i - 1];
            res += num[j];
            num.erase(j, 1);
        }
        return res;
    }

第k个排列（两个元素）

在A个a和B个b组成的所有字符串中，字典序第k个是什么？

例如：3个a，2个b，字典序第1个为aaabb，第二个为 aabab…

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
int a, b;
ll k, c[65][65]={1};

int main(){
    cin>>a>>b>>k;
    for(int i = 1; i <= a+b; ++i) {
        for(int j = 1; j <= i; ++j) {
            c[i][0]=1;
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    string s;
    while(a && b) {
        if (c[a+b-1][a-1] >= k) s += 'a', a--;
        else s += 'b', k -= c[a+b-1][a-1], b--;
    }
    s += string(a, 'a'), s += string(b, 'b');
    cout << s << "\n";
}

排列的字典序

求一个排列在所有 1 ~ n 的排列间的字典序排名。

康托展开 设有排列 p=a1 a2 ... an，那么对任意字典序比p小的排列，一定存在i,使得其前 i-1(1<= i < n)，位与p位对应位相同，第i位比pi小，后续位随意。于是对于任意i，满足条件的排列数就是从后n-i-1 位中选一个比ai小的数，并将剩下的n-i个数任意排列的方案数，即为 A[i]*(n-i)! (A[i]表示ai后面比ai小的数的个数)。遍历i即得总方案数。

总方案数加1即为排名。

例题

n个元素有n!种不同排列，将这n!个排列按照字典序排列，并编号为0,1,…,n!-1. 输入n个元素（1～n）的一个排列，计算出这个排列的字典序值。

例如 n = 3时, 123 编号为0，132编号为1, …, 321编号为5。

using ll = long long;
const int mod = 1e9 + 7;
int perm(vector<int> nums) {
    int n = nums.size();
    vector<ll> fac(n+1, 1), p(n);
    for (int i = 1; i <= n; ++i) 
        fac[i] = (fac[i - 1] * i) % mod;
    
    ll ans = 0;
    for (int i = 0; i < n; ++i) {  //预处理逆序对，可以用树状数组优化到nlog(n)
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] > nums[j]) 
                p[i]++;
        }
    }

    for (int i = 0; i < n; ++i) {
        ans += p[i] * fac[n - 1 - i];
    }
    return ans;
}

排列的字典序（有重复元素）

leetcode 1830

给你一个字符串s, 每次对s执行上一个排列的操作，求把s变为有序所需要的操作次数，由于答案可能会很大，请返回它对 1e9 + 7 取余的结果。

数据范围

1 <= s.length <= 3000
s 只包含小写英文字母

分析

实际上是求比s小的排列有多少个，即s是第多少个排列，

using ll =  long long;
const int MOD = 1e9 + 7, N = 3010;

class Solution {
public:
    ll f[N], g[N];
    ll qmi(ll a, int b) {
        ll res = 1;
        while (b) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    //全排列并去除重复项  n!/(n1! * n2! * ... * nm!)
    ll get(int cnt[]) {  
        ll res = 1, sum = 0;
        for (int i = 0; i < 26; i ++ ) sum += cnt[i];
        res = f[sum];
        for (int i = 0; i < 26; i ++ )
            res = res * g[cnt[i]] % MOD;
        return res;
    }
    
    int makeStringSorted(string s) {
        f[0] = g[0] = 1;  // 计算阶乘和相应的逆元
        for (int i = 1; i <= s.size(); i ++ ) { 
            f[i] = f[i - 1] * i % MOD;
            g[i] = qmi(f[i], MOD - 2);
        }
        
        ll res = 0;
        int cnt[26] = {0};
        for (auto c: s) cnt[c - 'a'] ++ ;
        
        for (int i = 0; i < s.size(); i ++ ) {
            int x = s[i] - 'a';
            for (int j = 0; j < x; j ++ ) {
                if (!cnt[j]) continue;
                cnt[j] -- ;
                res = (res + get(cnt)) % MOD;
                cnt[j] ++ ;
            }
            cnt[x] -- ;
        }
        return res;
    }
};

全排列（无重复）

LeetCode 46. 全排列

题目描述

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

示例:

输入: [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 是一个循环递归的过程

基于插入的写法

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

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp, nums;
    int n;
    void dfs(int u, int s) {
        if(u == n) {
            ans.push_back(tmp);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (!(s >> i & 1)) {
                tmp.push_back(nums[i]);
                dfs(u + 1, s | 1 << i);
                tmp.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& a) {
        nums = a;
        n = a.size();
        dfs(0,0); //from 0, state:0
        return ans;
    }
};

【注】关于 for(i=0;..) 与 for(i=step;..) 的说明

基于交换的写法

基于交换的写法，代码比较简洁，但个人认为有一点不好理解

  vector<vector<int>> res;
  void backtrack(vector<int>& nums, int begin) {
      if (begin >= nums.size()) {
          res.push_back(nums);
          return;
      }
      for (int i = begin; i < nums.size(); i++) {
          swap(nums[begin], nums[i]);
          backtrack(nums, begin + 1);
          swap(nums[begin], nums[i]);
      }
  }
  vector<vector<int>> permute(vector<int>& nums) {
      backtrack(nums, 0);
      return res;
  }

全排列（有重复）

LeetCode - 47. 全排列 II

题目描述

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

示例:

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

思路 1

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

思路 2

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

基于插入的写法

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> nums, tmp;
    int n;
    void dfs(int u, int s) {
        if (u == n) {
            ans.push_back(tmp);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (!(s >> i & 1)) {
                tmp.push_back(nums[i]);
                dfs(u + 1, s | 1 << i);
                while (i + 1 < n && nums[i + 1] == nums[i]) i++;
                tmp.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& _nums) {
        nums = _nums;
        n = nums.size();
        sort(nums.begin(), nums.end());
        dfs(0, 0);
        return ans;
    }
};

基于交换的写法

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> perms;
        permute(nums, 0, perms);
        return perms;
    }
    void permute(vector<int> nums, int i, vector<vector<int>>& perms) {
        if (i == nums.size()) {    // 注意这里nums 应该使用**值传递**
            perms.push_back(nums);
        } else {
            for (int j = i; j < nums.size(); j++) {
                if (j == i || nums[j] != nums[i]) {
                    swap(nums[i], nums[j]);  // nums传引用配合回溯无法得出正确结果
                    permute(nums, i + 1, perms); //原因在于此时会破坏剩余数组的有序性
                }                             
            }
        }
    }

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

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

子集

leetcode 78

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

1.迭代法（二进制）

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    t.push_back(nums[i]);
                }
            }
            ans.push_back(t);
        }
        return ans;
    }
};

时空复杂度

时间复杂度：O(n×2^n)。一共 2^n个状态，每种状态需要 O(n) 的时间来构造子集
空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价。

递归法实现子集枚举

class Solution {
public:
    vector<vector<int>> ans;
    int n;
    vector<int> nums;
    void dfs(int u, int s) {
        if (u == n) {
            vector<int> tmp;
            for (int i = 0; i < n; ++i) 
                if (s >> i & 1) tmp.push_back(nums[i]);
            ans.push_back(tmp);
            return;
        }
        dfs(u + 1, s);
        dfs(u + 1, s | 1 << u);
    }
    vector<vector<int>> subsets(vector<int>& _nums) {
        nums = _nums;
        n = nums.size();
        dfs(0, 0);
        return ans;
    }
};

时空复杂度

时间复杂度：O(n×2^n)。一共 2^n个状态，每种状态需要 O(n) 的时间来构造子集
空间复杂度：O(n)。临时数组 tt的空间代价是 O(n)，递归时栈空间的代价为 O(n)。

子集2

leetcode 90

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> nums;
    int n;
    void dfs(int u, int s) {
        if (u == n) {
            vector<int> tmp;
            for (int i = 0; i < n; ++i)
                if (s >> i & 1) tmp.push_back(nums[i]);
            ans.push_back(tmp);
            return;
        }
        dfs(u + 1, s | 1 << u);
        if(u && nums[u] == nums[u - 1] && s >> (u-1) & 1) return;
        dfs(u + 1, s);
    }
    vector<vector<int>> subsetsWithDup(vector<int>& _nums) {
        nums = _nums;
        sort(nums.begin(), nums.end());
        n = nums.size();
        dfs(0, 0);
        return ans;
    }
};

组合

组合（n 选 k，无重复）

LeetCode - 77. 组合

问题描述

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

示例:

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

思路

带回溯的深度优先搜索，类似全排列（无重复）

C++

    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();
        }
    }
    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，有重复）

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

acwing n选m，有重复

给定一个长度为 n 的可包含重复数字的序列，从中随机选取 m 个数字，输出所有可能的选择方案。

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m;
const int N = 30;
int a[N];

void dfs(int u, int cnt, int s) {
    if (cnt == m) {
        for (int i = 0; i < n; ++i) 
            if (s >> i & 1) cout << a[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = u; i < n; ++i) {
        if (i && !(s>>(i-1)&1) && a[i-1] == a[i]) continue;
        dfs(i + 1, cnt + 1, s | 1 << i);
    }
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);
    dfs(0, 0, 0);
    return 0;
}

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

LeetCode - 39. 组合总和

思路

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

C++

    vector<vector<int>> res;
    vector<int> path;
    void dfs(vector<int>& nums, int idx, int t) {
        if (t == 0) {
            res.push_back(path);
            return;
        }
        for (int i = idx; i < nums.size(); ++i) {
            if (nums[i] > t) break;
            path.push_back(nums[i]);
            dfs(nums, i, t - nums[i]);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& nums, int t) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0, t);
        return res;
    }

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

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

LeetCode - 40. 组合总和 II

思路

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

C++

    vector<vector<int> > res;
    vector<int> path;
    void dfs(vector<int>& nums, int idx, int t) {
        if (t == 0) {
            res.push_back(path);
            return;
        }
        for (int i = idx; i < nums.size(); ++i) {
            if (nums[i] > t) break;
            if (i > idx && nums[i] == nums[i - 1]) continue;
            path.push_back(nums[i]);
            dfs(nums, i + 1, t - nums[i]);
            path.pop_back();
        }
    }
    vector<vector<int> > combinationSum2(vector<int>& nums, int t) {
        sort(nums.begin(), nums.end());  // 因为存在重复，需要先排序
        dfs(nums, 0, t);
        return res;
    }

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

LeetCode - 216. 组合总和 III

问题描述

找出所有相加之和为 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]]

思路

在组合总和（数字不重复但可重复使用）上稍作修改即可

C++

    vector<vector<int>> res;
    vector<int> path;
    void dfs(int k, int idx, int n) {
       if (n == 0) {
           if (path.size() == k) res.push_back(path);
           return;
       }
       for (int i = idx; i <= 9; ++i) {
           if (i > n) break;
           path.push_back(i);
           dfs(k, i + 1, n - i);
           path.pop_back();
       }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, 1, n);
        return res;
    }

组合总和 4（动态规划）

LeetCode - 377. 组合总和 Ⅳ

问题描述

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:
nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

进阶：
  如果给定的数组中含有负数会怎么样？
  问题会产生什么变化？
  我们需要在题目中添加什么限制来允许负数的出现？

思路

这其实是一道动态规划问题

C++

类似与零钱兑换和背包问题

  int combinationSum4(vector<int>& nums, int target) {
      vector<unsigned long long> dp(target+1,0);
      dp[0] = 1;
      sort(nums.begin(), nums.end());
      for (int i = 1; i <= target; ++i) {
          for (int x : nums) {
              if (i >= x) {
                  dp[i] += dp[i - x];
              }
          }
      }
      return dp[target];
  }

–>

【说明】

字典序

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

高位与低位

对序列中任意两个位置而言，靠近左侧的为高位，靠近右侧的为低位
生成排列的过程就是不断增大高位，减小低位的过程
```
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 标记使用
- 全排列（无重复，基于插入的写法）
- 全排列（有重复，基于插入的写法）
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 个元素
- 在排列（无重复）问题中，使用的是 dfs(step+1)
- 在组合（无重复）问题中，使用的是 dfs(i+1)
- 相关代码段
```
// 排列
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)`

在组合总和问题中，还用到了 dfs(i)
```
for (int i = step; i < nums.size(); i++) {
    // ...
    dfs(nums, i);
    // ...
}
```
- 一方面，它跟组合问题类似，用过的数字不再使用；因此使用的是 i 而不是 step
- 另一方面，每个数字可以重复使用，因此使用的是 dfs(i) 而不是 dfs(i+1)

king-yyf

king-yyf

专题-排列组合

Index

排列

下一个排列

上一个排列

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

第k个排列

第k个排列（两个元素）

排列的字典序

排列的字典序（有重复元素）

全排列（无重复）

基于插入的写法

基于交换的写法

全排列（有重复）

基于插入的写法

基于交换的写法

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

子集

子集2

组合

组合（n 选 k，无重复）

组合（n 选 k，有重复）

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

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

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

【说明】

字典序

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

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

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

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

Index

排列

下一个排列

上一个排列

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

第k个排列

第k个排列（两个元素）

排列的字典序

排列的字典序（有重复元素）

全排列（无重复）

基于插入的写法

基于交换的写法

全排列（有重复）

基于插入的写法

基于交换的写法

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

子集

子集2

组合

组合（n 选 k，无重复）

组合（n 选 k，有重复）

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

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

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

【说明】

字典序

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

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

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

dfs(i+1) 和 dfs(i)

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

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

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

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