数据结构与算法——递归、回溯与分治汇总整理

预备知识:递归函数与回溯算法例1-a:求子集(medium)(回溯法、位运算法)例1-b:求子集2(medium)(回溯法)例1-c:组合数之和2(medium)(回溯法、剪枝)例2:生成括号(medium)(递归设计)例3:N皇后(hard)(回溯法)预备知识:分治算法与归并排序例4:逆序数(hard)(分治法、归并排序应用)

class Solution {
public:
    vector> subsets(vector& nums) {
        std::vector> result;//存储最终结果的result
        std::vector item;//回溯时产生各个子集的数组
        result.push_back(item);//将空集放入result
        generate(0, nums, item, result);
        return result;
    }
private:
    void generate(int i, std::vector& nums, 
    	std::vector& item, 
    	std::vector>& result) {
        if (i >= nums.size()) {
            return;
        }
        item.push_back(nums[i]);
        result.push_back(item);
        generate(i + 1, nums, item, result);
        item.pop_back();
        generate(i + 1, nums, item, result);
    }
};

在上一题的基础上扩大了条件，nums中可包含重复值。所带来的问题：

方案，先排序，在用set去重：

class Solution {
public:
    vector> subsetsWithDup(vector& nums) {
        std::vector> result;//存储最终结果的result
        std::vector item;//回溯时产生各个子集的数组
        std::set>res_set;//去重使用的集合
        std::sort(nums.begin(), nums.end());//排序
        result.push_back(item);//将空集放入result
        generate(0, nums, item, result, res_set);
        return result;
    }
private:
    void generate(int i, std::vector& nums, std::vector& item, std::vector>& result, std::set>& res_set) {
        if (i >= nums.size()) {
            return;
        }
        item.push_back(nums[i]);
        if (res_set.find(item) == res_set.end()) {
            result.push_back(item);
            res_set.insert(item);
        }
        generate(i + 1, nums, item, result, res_set);
        item.pop_back();
        generate(i + 1, nums, item, result, res_set);
    }
};

class Solution {
public:
    vector> combinationSum2(vector& candidates, int target) {
        std::vector> result;//存储最终结果的result
        std::vector item;//回溯时产生各个子集的数组
        std::set>res_set;//去重使用的集合
        std::sort(candidates.begin(), candidates.end());//排序
        generate(0, candidates, item, result, res_set, 0, target);
        return result;
    }
private:
    void generate(int i, std::vector& nums, std::vector& item, std::vector>& result, std::set>& res_set, int sum, int target) {
        if (i >= nums.size() || sum > target) {
            return;
        }
        sum += nums[i];
        item.push_back(nums[i]);
        if (target == sum && res_set.find(item) == res_set.end()) {
            result.push_back(item);
            res_set.insert(item);
        }
        generate(i + 1, nums, item, result, res_set, sum, target);
        sum -= nums[i];
        item.pop_back();
        generate(i + 1, nums, item, result, res_set, sum, target);
    }
};

class Solution {
public:
    vector generateParenthesis(int n) {
        vector result;
        generate("", n, n, result);
        return result;
    }
private:
    void generate(string item, int left, int right, vector& result) {
        if (left == 0 && right == 0) {
            result.push_back(item);
            return;
        }
        if (left > 0) {
            generate(item + '(', left - 1, right, result);
        }
        if (left < right) {
            generate(item + ')', left, right - 1, result);
        }
    }
};

力扣—— 51. N 皇后

力扣——315. 计算右侧小于当前元素的个数