C++ 递归、搜索与回溯:三剑客

1

2

3

4

intfact(intn) {

if(n == 0)return1;// 出口

returnn * fact(n - 1);// 递归式

}

1

2

3

4

5

6

7

8

9

10

11

voidbacktrack(路径, 选择列表) {

if(满足结束条件) {

记录答案;

return;

}

for(选择 : 选择列表) {

做选择;

backtrack(路径, 选择列表);

撤销选择;// 回溯核心

}

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

vector<vector<int>> res;

vector<int> path;

boolvis[10];

voiddfs(vector<int>& nums) {

if(path.size() == nums.size()) {

res.push_back(path);

return;

}

for(inti = 0; i < nums.size(); i++) {

if(vis[i])continue;

vis[i] = 1;

path.push_back(nums[i]);

dfs(nums);

path.pop_back();// 回溯

vis[i] = 0;

}

}

1

2

3

4

5

6

7

8

voiddfs(vector<int>& nums,intu) {

res.push_back(path);

for(inti = u; i < nums.size(); i++) {

path.push_back(nums[i]);

dfs(nums, i + 1);

path.pop_back();

}

}

1

2

3

4

intfib(intn) {

if(n <= 1)returnn;

returnfib(n-1) + fib(n-2);

}