代码随想录算法训练营第二十九天 | 491.递增子序列、46.全排列、47.全排列 II

491.递增子序列

题目链接：491.递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

文章讲解/视频讲解：https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html

思路

按照回溯的方法来解决。

用回溯的方式遍历数组nums构成的子序列的树的所有节点，然后判断每个节点是否构成有序。

横向遍历是遍历子序列当前下标，纵向遍历是递归寻找子序列的下一个下标。

这里需要判断去重，去重的方法是：横向遍历过程中，判断该下标对应的元素是否已遍历过，如果已遍历过，则跳过。因为对于同一层来说，元素如果重复，构成的子序列可能有重复

去重的判断可以按照我写的用循环来判断，也可以用一个哈希表来判断去重。

C++实现

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> path;
        backtracking(path, 0, nums);
        return results;
    }

    void backtracking(vector<int>& path, int starti, const vector<int>& nums){
        if(path.size() >= 2){
            if(isValid(path)) results.push_back(path);
        }

        for(int i = starti;i<nums.size();i++){
            if(i > starti){
                bool skip = false;
                for(int j = starti;j<i;j++){
                    if(nums[j] == nums[i]){
                        skip = true;
                        break;
                    }
                }
                if(skip) continue;
            }
            path.push_back(nums[i]);
            backtracking(path, i + 1, nums);
            path.pop_back();
        }
    }

    bool isValid(const vector<int>& path){
        for(int i = 1;i<path.size();i++){
            if(path[i] < path[i - 1]) return false;
        }
        return true;
    }
};

46.全排列

题目链接：46.全排列

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

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

文章讲解/视频讲解：https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html

思路

用回溯的方法，不过我这里使用的方法比较暴力。

回溯函数的参数只有当前组合path，以及对于数组nums的引用。

横向遍历是寻找组合的当前元素，纵向遍历是寻找下一个添加入组合的元素。

其中添加当前元素时的判断我写得很粗暴，只要当前元素不在path中，就添加入结果，开启下一层遍历。

当path的大小等于nums的大小时，将path添加进最终结果。

看了卡哥的教程，发现他也写得如此暴力。。不过，可以用一个used数组来判断元素是否加入过path。

C++实现

// 原写法
class Solution {
public:
    vector<vector<int>> results;
    vector<int> used;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        used.resize(nums.size(), false);
        backtracking(path, nums);
        return results;
    }

    void backtracking(vector<int> path, const vector<int>& nums){
        if(path.size() == nums.size()){
            results.push_back(path);
        }

        for(int i = 0;i<nums.size();i++){
            if(used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(path, nums);
            path.pop_back();
            used[i] = false;
        }
    }

    bool visited(const vector<int>& path, int element){
        for(int i = 0;i<path.size();i++){
            if(path[i] == element) return true;
        }
        return false;
    }
};

// 用used数组判断元素是否加入
class Solution {
public:
    vector<vector<int>> results;
    vector<int> used;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        used.resize(nums.size(), false);
        backtracking(path, nums);
        return results;
    }

    void backtracking(vector<int> path, const vector<int>& nums){
        if(path.size() == nums.size()){
            results.push_back(path);
        }

        for(int i = 0;i<nums.size();i++){
            if(used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(path, nums);
            path.pop_back();
            used[i] = false;
        }
    }
};

47.全排列 II

题目链接：47.全排列 II

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

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

文章讲解/视频讲解：https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html

思路

与上一题全排列类似的思路，回溯函数的参数中只有当前排列的路径path以及对原数组nums的引用。

分为横向和纵向两个维度的遍历，横向遍历是遍历当前元素，添加入路径path，纵向遍历是递归地遍历path的下一个元素。

横向遍历时使用一个used数组，来判断当前下标是否遍历过。此题给定的是一个包含重复数字的数组，因此还需要去重。

去重是横向遍历时需要做的事情，可以使用一个unordered_set，在每一层遍历时，判断当前遍历的元素是否已经遍历过，如果遍历过，那么就跳过。因为如果同一层遍历到重复的元素，最终的结果必定重复。

也可以不用unordered_set，对nums排序，然后在横向遍历时，判断当前元素与上一个元素是否相同，如果相同则跳过。

这个used[i-1] = true，used[i-1] = false的判断是真抽象，好难想。

本质上if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;与

if(i > 0 && nums[i] == nums[i - 1] && used[i - 1]) continue;这两条语句，保留的是两组相同的结果，但是路径不同。

如果用if(i > 0 && nums[i] == nums[i - 1]) continue;替代的话，等于是把这两组路径全丢弃了。

我之前用unordered_set来去重的方法，本质是判断同一层used[i- 1]是否使用过，与

if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;是等价的，路径相同。

C++实现

// 哈希表去重
class Solution {
public:
    vector<vector<int>> results;
    vector<bool> used;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> path;
        used.resize(nums.size(), false);
        backtracking(path, nums);
        return results;
    }

    void backtracking(vector<int>& path, const vector<int>& nums){
        if(path.size() == nums.size()){
            results.push_back(path);
            return;
        }

        unordered_set<int> hashSet;
        for(int i = 0;i<nums.size();i++){
            if(used[i]) continue;
            if(hashSet.find(nums[i]) != hashSet.end()) continue;
            hashSet.insert(nums[i]);
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(path, nums);
            path.pop_back();
            used[i] = false;
        }
    }
};

// 去重的第二种写法
class Solution {
public:
    vector<vector<int>> results;
    vector<bool> used;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> path;
        used.resize(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtracking(path, nums);
        return results;
    }

    void backtracking(vector<int>& path, const vector<int>& nums){
        if(path.size() == nums.size()){
            results.push_back(path);
            return;
        }

        for(int i = 0;i<nums.size();i++){
            // used[i - 1] == true，说明当前子树路径nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            if(!used[i]){
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(path, nums);
                path.pop_back();
                used[i] = false;
            }
        }
    }
};