LeetCode.78.90.47.39.40(递归&回溯)

回溯法模板

78.子集

class Solution {
  public:
    vector<vector<int>> subsets(vector<int> &nums) {
        vector<vector<int>> ans;
        ans.push_back({});
        for (int i = 0; i < nums.size(); i++)
            add(nums, ans, i, {nums[i]}, nums.size());
        return ans;
    }
    void add(vector<int> &nums, vector<vector<int>> &ans, int pos, vector<int> temp, int n) {
        ans.push_back(temp);
        for (int i = pos + 1; i < n; i++) {
            temp.push_back(nums[i]);
            add(nums, ans, i, temp, n);
            temp.pop_back();
        }
    }
    // 10/10 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 36.17 % of cpp submissions (7.1 MB)

90.子集-ii

class Solution {
  public:
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        ans.push_back({});
        for (int i = 0; i < nums.size(); i++)
            add(nums, ans, i, {nums[i]}, nums.size());
        return ans;
    }
    void add(vector<int> &nums, vector<vector<int>> &ans, int pos, vector<int> temp, int n) {
        for (int i = 0; i < ans.size(); i++)
            if (ans[i] == temp)
                return;
        ans.push_back(temp);
        for (int i = pos + 1; i < n; i++) {
            temp.push_back(nums[i]);
            add(nums, ans, i, temp, n);
            temp.pop_back();
        }
    }
    // 20/20 cases passed (4 ms)
    // Your runtime beats 56.65 % of cpp submissions
    // Your memory usage beats 52.06 % of cpp submissions (7.6 MB)
};

47.全排列-ii

class Solution {
  public:
    /* vector<vector<int>> permuteUnique(vector<int> &nums) {
        sample = nums;
        fun();
        for (auto &&i : result) {
            for (auto &&j : i) {
                j = nums[j];
            }
        }
        for (int i = 0; i < result.size(); i++) {
            for (int j = i + 1; j < result.size(); j++) {
                if (result[i] == result[j]) {
                    swap(result[j], result[result.size() - 1]);
                    result.pop_back();
                    j--;
                }
            }
        }
        return result;
    }
    vector<vector<int>> result;
    vector<int> path;
    vector<int> sample;
    void fun() {
        if (path.size() == sample.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < sample.size(); i++) {
            bool judge = 0;
            for (int j = 0; j < path.size(); j++) {
                if (i == path[j]) {
                    judge = 1;
                    break;
                }
            }
            if (judge)
                continue;
            path.push_back(i);
            fun();
            path.pop_back();
        }
    }
    // 33/33 cases passed (980 ms)
    // Your runtime beats 5.1 % of cpp submissions
    // Your memory usage beats 5.01 % of cpp submissions (32.3 MB) */
    /* vector<vector<int>> result;
    vector<int> path;
    vector<int> sample;
    void fun() {
        if (path.size() == sample.size()) {
            vector<int> temp(path.size());
            int i = 0;
            for (auto &&n : temp) {
                n = sample[path[i++]];
            }
            for (auto &&n : result) {
                if (n == temp)
                    return;
            }
            result.push_back(temp);
            return;
        }
        for (int i = 0; i < sample.size(); i++) {
            bool judge = 0;
            for (int j = 0; j < path.size(); j++) {
                if (i == path[j]) {
                    judge = 1;
                    break;
                }
            }
            if (judge)
                continue;
            path.push_back(i);
            fun();
            path.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        sample = nums;
        fun();
        return result;
    }
    // 33/33 cases passed (804 ms)
    // Your runtime beats 5.1 % of cpp submissions
    // Your memory usage beats 5.01 % of cpp submissions (19.8 MB)
    //*寄 */
    vector<vector<int>> ans;
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        perm(nums, 0, nums.size() - 1);
        return ans;
    }

    void perm(vector<int> nums, int left, int right) {
        if (left == right)
            ans.push_back(nums);
        else {
            for (int i = left; i <= right; i++) {
                if (i != left && nums[left] == nums[i])
                    continue;
                swap(nums[left], nums[i]);
                perm(nums, left + 1, right);
            }
        }
    }
    // 33/33 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 28.08 % of cpp submissions (9.3 MB)
    //淦，左右指针
};

39.组合总和

class Solution {
  public:
    /* vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        auto ans = fun(candidates, target);
        for (int i = 0; i < ans.size(); i++) {
            vector<int> hashBefore(201, 0);
            cout << endl;
            for (auto k : ans[i])
                hashBefore[k]++;
            for (int j = i + 1; j < ans.size(); j++) {
                vector<int> hashBehind(201, 0);
                for (auto k : ans[j])
                    hashBehind[k]++;
                if (hashBefore == hashBehind) {
                    swap(ans[j], ans[ans.size() - 1]);
                    ans.pop_back();
                    j--;
                }
            }
        }
        return ans;
    }
    vector<vector<int>> fun(vector<int> &candidates, int target) {
        if (target <= 0)
            return {};
        vector<vector<int>> ans;
        for (int i = 0; i < candidates.size(); i++) {
            if (candidates[i] < target) {
                auto nextTemp = fun(candidates, target - candidates[i]);
                for (int j = 0; j < nextTemp.size(); j++) {
                    nextTemp[j].push_back(candidates[i]);
                    ans.push_back(nextTemp[j]);
                }
            } else if (candidates[i] == target) {
                ans.push_back({target});
            }
        }
        return ans;
    }
    // 170/170 cases passed (1328 ms)
    // Your runtime beats 5.02 % of cpp submissions
    // Your memory usage beats 4.95 % of cpp submissions (399.2 MB)
    //…… */
    /* vector<vector<int>> ans;
    vector<vector<int>> hash;
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        int ansSize = 0;

        fun(vector<int>(201, 0), {}, candidates, target);
        return ans;
    }
    void fun(vector<int> pathHash, vector<int> path, vector<int> &candidates, int target) {
        if (target <= 0)
            return;
        for (int i = 0; i < candidates.size(); i++) {
            if (candidates[i] < target) {
                path.push_back(candidates[i]);
                pathHash[candidates[i]]++;
                fun(pathHash, path, candidates, target - candidates[i]);
                path.pop_back();
                pathHash[candidates[i]]--;
            } else if (candidates[i] == target) {
                path.push_back(candidates[i]);
                pathHash[candidates[i]]++;
                bool exist = 0;
                for (int i = 0; i < ans.size(); i++) {
                    if (pathHash == hash[i]) {
                        exist = 1;
                    }
                }
                if (!exist) {
                    ans.push_back(path);
                    hash.push_back(pathHash);
                }

                path.pop_back();
                pathHash[candidates[i]]--;
            }
        }
    }
    // 170/170 cases passed (276 ms)
    // Your runtime beats 5.02 % of cpp submissions
    // Your memory usage beats 4.95 % of cpp submissions (202.3 MB)
    //*我吐了 */
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int> &candidates, int target, int sum, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < candidates.size(); i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
            sum -= candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0, 0);
        return result;
    }
    // 170/170 cases passed (4 ms)
    // Your runtime beats 91.68 % of cpp submissions
    // Your memory usage beats 70.97 % of cpp submissions (10.7 MB)
    //*用startIndex避免平方次搜索
};

40.组合总和-ii

class Solution {
  public:
    vector<int> path;
    vector<vector<int>> ans;
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        fun(candidates, target, 0);
        return ans;
    }
    void fun(vector<int> &candidates, int target, int startIndex) {
        if (target == 0) {
            ans.push_back(path);
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = startIndex; i < candidates.size(); i++) {
            if (i - 1 >= startIndex && candidates[i] == candidates[i - 1])
                continue;
            path.push_back(candidates[i]);
            fun(candidates, target - candidates[i], i + 1);
            path.pop_back();
        }
    }
    // 175/175 cases passed (4 ms)
    // Your runtime beats 89.21 % of cpp submissions
    // Your memory usage beats 87.45 % of cpp submissions (10.3 MB)
    //*这题就是39+47的组合
};