文章目錄

• • • • 1.預備知識
      • • 1.1 遞歸
        • 1.2 回溯
        • 1.3 位運算
      • 2.子集
      • • 2.1 題目描述
        • 2.2 解題思路——回溯遞歸法
        • 2.3 C++實現
        • 2.4 解題思路——位運算法
        • 2.5 位運算實現
      • 3.子集 II
      • • 3.1 題目描述
        • 3.2 解題思路
        • 3.3 回溯遞歸法——C++實現
        • 3.4 位運算——C++實現
      • 4.組合總和 II
      • • 4.1 題目描述
        • 4.2 解題思路
        • 4.3 C++實現
      • 5.括號生成
      • • 5.1 題目描述
        • 5.2 解題思路
        • 5.3 C++實現
      • 6.N 皇后
      • • 6.1 題目描述
        • 6.2 棋盤和皇后表示
        • 6.3 回溯算法
        • 6.4 C++實現
      • 7.
      • • 7.1 預備知識
        • 7.2 題目描述
        • 7.3 C++實現

1.預備知識

1.1 遞歸

1.2 回溯

1.3 位運算

2.子集

2.1 題目描述

給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。

解集 不能 包含重復的子集。你可以按 任意順序 返回解集

2.2 解題思路——回溯遞歸法

2.3 C++實現

class Solution { public:vector<vector<int>> subsets(vector<int>& nums) {vector<int> item;vector<vector<int>> result;result.push_back(item);generate(0,nums,item,result);return result;} private:void generate(int i,vector<int>& nums,vector<int>& item,vector<vector<int>>& 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);} };

2.4 解題思路——位運算法

2.5 位運算實現

class Solution { public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> result;//int all_set=pow(2,nums.size());int all_set=1<<nums.size();for(int i=0;i<all_set;i++){vector<int> item;for(int j=0;j<nums.size();j++){if(i&(1<<j)){item.push_back(nums[j]);}}result.push_back(item);}return result;}};

3.子集 II

3.1 題目描述

給定一個可能包含重復元素的整數數組 nums，返回該數組所有可能的子集（冪集）。

說明：解集不能包含重復的子集。

3.2 解題思路

3.3 回溯遞歸法——C++實現

class Solution { public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<int> item;vector<vector<int>> result;set<vector<int>> res_set;sort(nums.begin(),nums.end());result.push_back(item);generate(0,nums,item,result,res_set);return result;} private:void generate(int i,vector<int>& nums,vector<int>& item,vector<vector<int>>& result,set<vector<int>>& 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);} };

3.4 位運算——C++實現

class Solution { public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {int all_set;vector<vector<int>> result;set<vector<int>> res_set;sort(nums.begin(),nums.end());all_set=1<<nums.size();for(int i=0;i<all_set;i++){vector<int> item;for(int j=0;j<nums.size();j++){if(i&(1<<j)){item.push_back(nums[j]);}}if(res_set.find(item)==res_set.end()){result.push_back(item);res_set.insert(item); }}return result;} };

4.組合總和 II

4.1 題目描述

給定一個數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中只能使用一次。

所有數字（包括目標數）都是正整數。
解集不能包含重復的組合。

4.2 解題思路

4.3 C++實現

class Solution { public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<int> item;vector<vector<int>> result;set<vector<int>> res_set;sort(candidates.begin(),candidates.end());generate(0,candidates,item,result,res_set,0,target);return result;} private:void generate(int i,vector<int>& candidates,vector<int>& item,vector<vector<int>>& result,set<vector<int>>& res_set,int sum, int target){if(i>=candidates.size()||sum>target){return;}sum+=candidates[i];item.push_back(candidates[i]);if(sum==target&&res_set.find(item)==res_set.end()){result.push_back(item);res_set.insert(item);}generate(i+1,candidates,item,result,res_set,sum,target);sum-=candidates[i];item.pop_back();generate(i+1,candidates,item,result,res_set,sum,target);} };

5.括號生成

5.1 題目描述

數字 n 代表生成括號的對數，請你設計一個函數，用于能夠生成所有可能的并且 有效的 括號組合。

輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]

5.2 解題思路

輸出所有組合

5.3 C++實現

class Solution { public:vector<string> generateParenthesis(int n) {vector<string> result;generate("",n,n,result);return result;} private:void generate(string item,int left,int right,vector<string>& 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);}} };

6.N 皇后

6.1 題目描述

n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個整數 n ，返回所有不同的 n 皇后問題 的解決方案。

每一種解法包含一個不同的 n 皇后問題 的棋子放置方案，該方案中 ‘Q’ 和 ‘.’ 分別代表了皇后和空位。

1 <= n <= 9
皇后彼此不能相互攻擊，也就是說：任何兩個皇后都不能處于同一條橫行、縱行或斜線上。

6.2 棋盤和皇后表示

6.3 回溯算法

6.4 C++實現

class Solution { public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> result;vector<vector<int>> mark;vector<string> location;for(int i=0;i<n;i++){mark.push_back((vector<int>()));for(int j=0;j<n;j++){mark[i].push_back(0);}location.push_back("");location[i].append(n,'.');}generate(0,n,location,result,mark);return result;} private:void put_down_the_queen(int x,int y,vector<vector<int>>&mark){static const int dx[]={-1,1,0,0,-1,-1,1,1};static const int dy[]={0,0,-1,1,-1,1,-1,1};mark[x][y]=1;int new_x,new_y;for(int i=1;i<mark.size();i++){for(int j=0;j<8;j++){new_x=x+i*dx[j];new_y=y+i*dy[j];if(new_x>=0&&new_x<mark.size()&&new_y>=0&&new_y<mark.size()){mark[new_x][new_y]=1;}}}}void generate(int k,int n,vector<string> &location,vector<vector<string>> &result,vector<vector<int>> &mark){if(k==n){result.push_back(location);return;}for(int i=0;i<n;i++){if(mark[k][i]==0){vector<vector<int>> tmp_mark=mark;location[k][i]='Q';put_down_the_queen(k,i,mark);generate(k+1,n,location,result,mark);mark=tmp_mark;location[k][i]='.';}}} };

7.

7.1 預備知識

#include<vector>void merge_sort_two_vec(vector<int> &sub_vec1,vector<int> &sub_vec2,vector<int> &vec){int i=0,j=0;while(i<sub_vec1.size()&&j<sub_vec2.size()){if(sub_vec1[i]<=sub_vec2[j]){vec.push_back(sub_vec1[i]);i++;} else{vec.push_back(sub_vec2[j]);j++;} } for(;i<sub_vec1.size();i++){vec.push_back(sub_vec1[i]);} for(;j<sub_vec2.size();j++){vec.push_back(sub_vec2[j]);} }

7.2 題目描述

給定一個整數數組 nums，按要求返回一個新數組 counts。數組 counts 有該性質： counts[i] 的值是 nums[i] 右側小于 nums[i] 的元素的數量。

輸入：nums = [5,2,6,1]
輸出：[2,1,1,0]
解釋：
5 的右側有 2 個更小的元素 (2 和 1)
2 的右側僅有 1 個更小的元素 (1)
6 的右側有 1 個更小的元素 (1)
1 的右側有 0 個更小的元素

7.3 C++實現

代碼實現

總結

以上是生活随笔為你收集整理的数据结构与算法——递归、回溯与分治的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。