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

116 阅读 0 评论 77 点赞

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

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

leetcode 39 40 46 47 48 78 90

通用解法：回溯法

记得画图：状态树

复制代码

1
2
3
4
5
6
7
8
9
10
11
//回溯法模板
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表) 递归
        撤销选择

全排列问题

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//通用解法：回溯
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的组合

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//通用解法:回溯法（递归 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/

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//法一 数学归纳法
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();
    }
}