讨论/《队列 & 栈》 - 目标和/
《队列 & 栈》 - 目标和

用的是递归的方法,暴力搜索出每一种组合,但用完就有点后怕了,这里调用栈的深度等于数组的长度;这道题中数组的长度不超过20,而如果面对数组长度很大的情况,调用栈很容易溢出。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        binTravel(nums, S, 0, 0);
        return result;
    }
    void binTravel(vector<int>& nums,int S,int index, int sum){
        if(index==nums.size() && sum==S){
            result+=1;
        }
        else if(index<nums.size()){
            binTravel(nums, S, index+1, sum+nums[index]);
            binTravel(nums, S, index+1, sum-nums[index]);
        }
    }
private:
    int result;
};
展开全部 8 讨论