回溯法1

给定一个含n个整数的数组 nums（1≤n≤20，0≤nums[i]≤1000）和一个整数s（-1000≤s≤1000）。向数组中的每个整数前添加'+'或'-'，然后串联起所有整数，可以构造一个表达式，例如，nums={2，1}，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式 "+2-1"。输出满足条件的解的式子。

   设计一个算法求可以通过上述方法构造的运算结果等于s的不同表达式的数目。

 1 #include<vector>
 2 #include<iostream>
 3 using namespace std;
 4 class Solution {
 5     int ans=0;                //存放解个数
 6     vector<vector<int>>A;
 7     vector<int>current_ans;
 8 public:
 9     int findTargetSumWays(vector<int>& nums,int s) {
10         dfs(nums,s,0,0);
11         return ans;
12     }
13 
14     void  dfs(vector<int>& nums,int s,int i,int expv) {    
15         if (i==nums.size()) { //到达一个叶子结点
16             if(expv==s){
17                   ans++;
18                 A.push_back(current_ans);
19             }       //找到一个解
20         }
21         else {
22               current_ans.push_back(nums[i]);       //nums[i]前选择'+'
23             dfs(nums,s,i+1,expv+nums[i]);
24             current_ans.pop_back();      //回溯
25         
26             current_ans.push_back(-nums[i]);            //nums[i]前选择'-'
27             dfs(nums,s,i+1,expv-nums[i]);
28             current_ans.pop_back();            //回溯
29         }
30     }
31     void printfAns(){
32         for(const auto& a : A){
33             for(const auto& num : a){
34                 if(num > 0)
35                     cout << "+" ;
36                 cout << num;
37             }
38             cout << "\n";
39         }
40     }
41     
42 };
43 int main(){
44     Solution solution;
45     vector<int>nums = {1, 2, 1, 2, 1};
46     int target = 2;
47     cout << "符合条件的表达式共有" << solution.findTargetSumWays(nums,target) << "条：";
48     solution.printfAns();
49     return 0;
50 }