0%

相关的编程题汇总-回朔

发表于 更新于 分类于 ，

记录了回朔类的题目，常见的 八皇后问题，排列组合等

复原IP地址

全排列 II

​ 使用 swap 的方法全排列 去重的关键在于两点 一是和首元素相同的 不再swap 而是swap过的元素不再swap

组合总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> re;

    void dfs(vector<int>& candidates, vector<int>& se, int tg, int sel){
        if(tg == 0){
            re.push_back(se);
            return;
        }
        for(int i = sel; i < candidates.size(); i++){
            if(tg < candidates[i])  continue;
            se.push_back(candidates[i]);
            dfs(candidates, se, tg - candidates[i], i);   ////  i  关键  第一次 取 i 了之后  后面取的第二个 第三个...数 都只能从 第i 以及 i 之后开始取  比如 第一次取得第 2个数  那么第二次 就只能在 第二个 以及 第二个之后的数中取，因为 第二次再取第一个数的话 ，就 和 第一次取的第一个的情况重复
            se.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> tmp;
        dfs(candidates, tmp, target, 0);
        return re;
    }
};

组合总和 II

​ 相对上一个题 去重的关键是 要 先 排序 相同的元素在一起 ，才方便去重。

划分为k个相等的子集

暴力回朔，问题在于要 先排序 并且将大的放前面才不会超时。

子集

思路：对于每个位置的元素 由选和不选两种情况，选的话，就 push_back到缓存数组中，然后从下一个元素递归。如果不选当前元素，就要pop出来，再对从下一个元素递归。同理下一个元素也有选和不选两种状态。最终结束的标志就是 遍历完整个数组长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> re;
    
    void dfs(int sel, vector<int>& nums, vector<int>& ans){
        if(sel >= nums.size()){
            re.push_back(ans);
            return;
        }
               
        ans.push_back(nums[sel]);
        dfs(sel+1, nums, ans);
        ans.pop_back();
        dfs(sel+1, nums, ans);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> ans;
        dfs(0, nums, ans);
        return re;
    }
};

括号生成

和上面的题很类似，就通过回朔的方法，枚举当前位置是 左括号 or 右括号，分别进行递归。但是要满足有效的条件，就额外增加条件约束，即 只有左括号数量大于右括号的数量的时候才能再添加右括号，当左括号数量大于整体数量一半的时候 不能再添加左括号。