数据结构与算法之回溯解决全排列/组合/子集问题

84 阅读 0 评论 56 点赞

我是靠谱客的博主机智钻石，最近开发中收集的这篇文章主要介绍数据结构与算法之回溯解决全排列/组合/子集问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

回溯法解决全排列/组合/子集问题

leetcode 39 40 46 47 48 78 90

通用解法：回溯法

记得画图：状态树

//回溯法模板
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表) 递归
        撤销选择

全排列问题

输出[1,n]中所有的全排列。

//通用解法：回溯
vector<vector<int> > permute(int n){
    if(n < 1) return {};
    vector<vector<int> > res;   //存储最终结果
    vector<int> path;   //存储路径
    vector<bool> flag(n + 1, true);    //重要: 标记数组,用于标记是否选择，已经选择记为false，未选择记为true
    getPermute(res, path, flag, n);
    return res;
}

void getPermute(vector<vector<int> > &res, vector<int> &path, vector<bool> &flag, int n){
   if(path.size() == n){    
        res.push_back(path);
        return;
   }
   for(int i = 1; i < flag.size(); i++){    //选择列表。因为是全排列，每次都要从头遍历判断是否可以选择
       if(flag[i] == true){     //若未选择则加入路径，已经选择就跳过
           path.push_back(i);
           flag[i] = false;
           getPermute(res, path, flag, n);	//dfs
           //回溯
           flag[i] = true;
           path.pop_back();
       }
   }
}

n皇后问题

组合问题

求[1,n]的所有长度为k的组合

//通用解法:回溯法（递归 dfs）
vector<vector<int> > combine(int n, int k){
    if(n < 1 || k < 1) return {};
    vector<vector<int> > res;
    vector<int> path;
    getCombine(res, path, n, k, 1);
    return res;
}

//n限制了树的宽度（每次的选择个数），k限制了树的高度（递归的深度）
void getCombine(vector<vector<int> > &res, vector<int> &path, int n, int k, int start){
    if(path.size() == k){
        res.push_back(path);
        return;
    }
    for(int i = start; i <= n; i++){ //选择列表， 每递归一层都会有新的选择列表
        //进行选择
        path.push_back(i);
        //递归 dfs
        getCombine(res, path, n, k, i + 1);
        //回溯 
        path.pop_back();
    }
}

子集问题

求给定集合的所有子集，如Input: nums = [1,2,3] Output:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [ ] ]

https://leetcode-cn.com/problems/subsets/solution/hui-su-si-xiang-tuan-mie-pai-lie-zu-he-zi-ji-wen-t/

//法一 数学归纳法
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int> > result;
    result.push_back({});
    sort(nums.begin(), nums.end());
    for(int x : nums){
        int count = result.size();
        for(int i = 0; i < count; i++){
            vector<int> temp = result[i];
            temp.push_back(x);
            result.push_back(temp);
        }
    }
    return result;
}

//法二 通用解法：回溯（递归 dfs）
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int> > res;
    vector<int> path;//保存路径
    sort(nums.begin(), nums.end());
    getSubset(res, path, nums, 0);
    return res;
}
void getSubset(vector<vector<int> > &res, vector<int> &path, vector<int> &nums, int start){
    res.push_back(path);
    for(int i = start; i < nums.size(); ++i){
        //进行选择
        path.push_back(nums[i]);
        //递归 dfs
        getSubset(res, path, nums, i + 1);
        //回溯 回到上一个节点
        path.pop_back();
    }
}

时间复杂度：
$2^N)$
空间复杂度：
$2^N)$