力扣排列组合问题梳理（超详细）

算法
Word count: 2.3k   |   Reading time≈ 10 min

说明：本文基于慕课《玩转算法面试 从真题到思维全面提升算法思维》，并加入了一些自己的理解。

递归与回溯框架

对于递归本身，可以结合二叉树的性质去理解，不是本文讨论的重点。本文讨论了更一般的递归问题和回溯的算法思想，这些问题在本质上也属于树形问题。顾名思义，对于问题解的讨论可以用一颗树来进行表示。来看一些例题

17. Letter Combinations of a Phone Number

给出一个数字字符串，返回这个数字字符串能表示的所有字母组合

在梳理算法思路时还要确定以下情况的处理：

  • 字符串的合法性
  • 空字符串
  • 多个解的顺序

这是一个典型的树形问题，例如对于字符串”23“而言，字符"2"能表示字符"a", “b”, “c”。字符"3"能表示"d",“e”,“f”。

那么就能构建出图中所示的一棵树，用digits表示数字字符串，s(digits)是digits所能代表的字母字符串，则

s(digits[0,...,n−1])=letter(digits[0])+s(digits[1,...,n−1])=letter(digits[0])+letter(digits[1])+s[digits[2,...,n−1]]\begin{aligned} &s(digits[0, ..., n-1])\\ &=letter(digits[0]) + s(digits[1, ..., n-1])\\ &=letter(digits[0]) + letter(digits[1]) + s[digits[2, ..., n-1]] \end{aligned}

在上述公式中，求解s(digits[0,...,n−1])s(digits[0,...,n-1])需要递归调用s(digits[1,...,n−1])s(digits[1,...,n-1])，以此类推。代码如下

点击查看代码
vector<string> ans;
    unordered_map<char, string> dict;
    void dfs(string digits, int depth, string &curStr){
        if(depth == digits.size()){
            ans.push_back(curStr);
            return;
        }
        for(auto ch:dict[digits[depth]]){
            curStr[depth] = ch;
            dfs(digits, depth+1, curStr);
        }
    }
    vector<string> letterCombinations(string digits) {
        int n = digits.size();
        if(n == 0) return ans;
        string str(n, '#');
        dict['2'] = "abc";
        dict['3'] = "def";
        dict['4'] = "ghi";
        dict['5'] = "jkl";
        dict['6'] = "mno";
        dict['7'] = "pqrs";
        dict['8'] = "tuv";
        dict['9'] = "wxyz";
        dfs(digits, 0, str);
        return ans;
    }
点击查看代码

回溯法是暴力解法的一个主要实现手段

Restore IP Addresses

给一个数字字符串，为这个数字子字符串加上三个点，使其成为一个合法的ip地址，返回所有的合法ip地址

  • 如给定字符串"25525511135"
  • 返回{“255.255.11.135”, “255.255.111.35”}

Palindrome Partitioning

给出一个字符串，拆分这个字符串，使得所有拆分的子串都是回文字符串，返回所有的拆分可能

  • 给定字符串s=“aab”
  • 结果为[[“aa”, “b”], [“a”, “a”, “b”]]

排列问题

Permutations

给定一个整形数组，其中各个元素都不相同，返回这些元素所有排列的可能。全排列问题，其递归形式为

Image

注意变量的恢复

Permutations II

给定一个整型数组，其中可能有相同的元素，返回这些元素所有排列的可能

  • 如对于[1,1,2]
  • 返回[[1,1,2],[1,2,1],[2,1,1]]

组合问题

给出两个整数n和k，求在1…n这n个数字中选出k个数字的所有组合

  • 如n=4, k = 2
  • 结果为[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

注意不能重复，因此每次从上一个数字之后开始取，但当n和k的规模大了以后就会比较吃力，采用回溯法的剪支

点击查看代码
vector<vector<int>> ans;
int n, k;
void getComb(int depth, vector<int>& tmp, int start){
    if(depth == k){
        ans.push_back(tmp);
        return;
    }
    // 当前已经有tmp.size()个元素，还要在[1,n]中找出k-tmp.size()个
    // 则i最多为n - (k-c.size()) + 1
    for(int i = start;i <= n - (k-c.size()) + 1;i++){
        tmp.push_back(i);
        getComb(depth+1, tmp, i);
        tmp.pop_back();
    }
}
vector<vector<int>> combine(int n, int k) {
    this->n = n;
    this->k = k;
    vector<int> tmp;
    getComb(0, tmp, 1);
    return ans;
}
点击查看代码

39. Combination Sum

给出一个集合，其中所有的元素各不相同，以及一个数字T。寻找所有该集合中的元素组合，使得组合中的所有元素和为T。（注意集合中每一个元素可以使用多次）

  • 如给定集合nums=[2,3,6,7], T=7
  • 返回[[7], [2,2,3]]
  • 代码，排序加快搜索速度
点击查看代码
vector<vector<int>> ans;
int n;
void dfs(vector<int>& arr, int target, vector<int> &tmp, int index){
    if(target == 0){
        ans.push_back(tmp);
        return;
    }
    for(int i = index;i < n && target-arr[i]>=0;i++){
        tmp.push_back(arr[i]);
        dfs(arr, target-arr[i], tmp, i);
        tmp.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    n = candidates.size();
    sort(candidates.begin(), candidates.end());
    vector<int> tmp;
    dfs(candidates, target, tmp, 0);
    return ans;
}
点击查看代码

40. Combination Sum II

给出一个集合，其中元素可能相同，以及一个数字T。寻找所有该集合中的元素组合，使得组合中所有元素的和为T。（注意：集合中每一个元素只能用一次）

  • 代码——巧妙地去重
点击查看代码
vector<vector<int>> ans;
    void dfs(vector<int>& arr, int target, vector<int>& tmp, int index){
        if(target == 0){
            ans.push_back(tmp);
            return;
        }
        for(int i = index;i < arr.size() && target-arr[i] >= 0;i++){
            if(i > 0 && arr[i] == arr[i-1]) continue;
            if(arr[i] != 0){
                int copy = arr[i];
                arr[i] = 0;
                tmp.push_back(copy);
                dfs(arr, target-copy, tmp, i+1);
                arr[i] = copy;
                tmp.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        int n = candidates.size();
        sort(candidates.begin(), candidates.end()); // 排个序，加快搜索效率
        vector<int> tmp;
        dfs(candidates, target, tmp, 0);
        return ans;
    }
点击查看代码

216. Combination Sum III

在1-9这九个数字中，选出k个数字，每个数字只能使用一次，使得其和为n

  • 如n=7, k = 3, 结果为【【1，2，4】】
  • 代码
点击查看代码
vector<vector<int>> ans;
vector<bool> flag;
void dfs(int k, int n, int index, vector<int> &tmp){
    if(k == 0){
        if(n == 0) ans.push_back(tmp);
        return;
    }
    for(int i = index;i <= 9;i++){
        if(!flag[i]){
            flag[i] = true;
            tmp.push_back(i);
            dfs(k-1, n-i, i, tmp);
            tmp.pop_back();
            flag[i] = false;
        }
    }
}
vector<vector<int>> combinationSum3(int k, int n) {
    flag = vector<bool>(10, false);
    vector<int> tmp;
    dfs(k, n, 1, tmp);
    return ans;
}
点击查看代码

377. Combination Sum IV

给定一组不同的整数 nums 和一个目标整数目标，返回加起来为目标的可能组合数。 答案保证适合 32 位整数。

  • 如nums = [1,2,3], target = 4，结果为7
点击查看代码
int ans;
void dfs(vector<int>& nums, int target, vector<int> &tmp){
    if(target == 0){
        ans++;
        return;
    }
    for(int i = 0;i < nums.size() && target-nums[i]>=0;i++){
        tmp.push_back(nums[i]);
        dfs(nums, target-nums[i], tmp);
        tmp.pop_back();
    }
}
int combinationSum4(vector<int>& nums, int target) {
    vector<int> tmp;
    sort(nums.begin(), nums.end());
    ans = 0;
    dfs(nums, target, tmp);
    return ans;
}
点击查看代码

上面四个力扣的组合问题是递归问题中的典型代表，通过对这些题目的理解和细节对比能够轻而易举总结处一套模板出来。尽管在Combination Sum IV中这样的模板因超时而无法AC，但这并不影响我们对这一类问题的理解。仔细观察这些题目中细微的区别与解法的调整，这是模板定制的基本功。下面再次的进行梳理：

  1. 对于数组中有重复元素，但每个只能使用一次（Combination Sum II）
  2. 数组数字各不相同，数字可以重复使用，结果可以重复（Combination Sum IV）
  3. 数组数字各不相同，数字可以重复使用，结果不可以重复（Combination Sum）
  4. 对于数字各不相同，且不能重复使用（Combination Sum III）

从上面这四种条件中，我整理出以下的应对方案：

1.对于数组中有重复元素的情况，如果不加以区别，会造成重复的结果，举例来说[1,1,2,5,7]要凑成8。直接套用模板时难免出现结果中有两个[1,2,5],[1,7]的情况。这时候可以在循环中加入去重的语句，避免同一个数字重复的在一次搜索中两次作为起点，也就是

if(i > 0 && arr[i] == arr[i-1]) continue;

2.对于结果可以重复的就是模板直接求出来的结果

3.对于不可以重复，可以在递归过程中引入index来标记上一次查的位置，让每次新的位置只能在上一次之后，就避免了结果重复的问题，见Combination Sum II。

组合问题是计算机中一类比较重要的问题，它的扩展问题可以是子集问题（No. 78, No. 90）,也可以是岛屿问题（No. 200, No. 305, No. 694）等等，尽管形式丰富，但主要是围绕递归和回溯来展开的，以点及面可以逐步解决此类问题。

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2015-2024 YuleZhang's Blog
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信