Simple AC C++ backtracking solution


  • 0
    K
    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int S) {
            int count = 0;
            if (nums.empty())
            {
                return count;
            }
            int curSum = 0;
            GetCount(nums, 0, curSum, S, &count);
            return count;
        }
    private:
        void GetCount(vector<int>& nums, int index, int curSum, int target, int* numWays)
        {
            if (index >= nums.size())
            {
                if (curSum == target)
                {
                    *numWays += 1;
                }
                return;
            }
            GetCount(nums, index+1, curSum+nums[index], target, numWays);
            GetCount(nums, index+1, curSum-nums[index], target, numWays);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.