题目

https://leetcode-cn.com/problems/target-sum/

目标和

代码

class Solution {
public:

    int findTargetSumWays(vector<int>& nums, int S) {
        int count=0;
        search(0,nums,0,S,count);
        return count;
    }

    void search(int k,vector<int>& nums,int sum,int s,int &count){
        if(k==nums.size()){
            if(sum==s) count++;
            return;
        }
        for(int i=0;i<=1;i++){
            if(i==0){
                sum+=nums[k];
                search(k+1,nums,sum,s,count);
                sum-=nums[k];
            }else{
                sum-=nums[k];
                search(k+1,nums,sum,s,count);
                sum+=nums[k];
            }
        }
    }
};

简析

套用标准的搜索模版写即可

A for循环范围

这里把有限的选择转化成一个for循环，即可以选择+或者-，那我们的for循环范围就是0到1；

for(int i=0;i<=1;i++)

B 选择后的变化

sum的值相应的+或-即可，然后搜索下一层

 if(i==0){
     sum+=nums[k];
}

C 结束条件

如果k层等于数组长度，即都已经搜索完，判断结果是否等于给定结果

if(k==nums.size()){
  if(sum==s) count++;
  return;
}

D 回溯

• 需要回溯，每一个位置的+或-，都可重新选择
• 回溯方法，sum中把这个值还原即可

           if(i==0){
                sum+=nums[k];
                search(k+1,nums,sum,s,count);
                sum-=nums[k];
            }else{
                sum-=nums[k];
                search(k+1,nums,sum,s,count);
                sum+=nums[k];
            }