You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
思路：本题使用动态规划以及深度优先搜索的思想，对数组中的每一个元素分为正号和负号，递归进行相加，判断最终结果与S是否相同。
void help(vector<int>&nums, int S, int &count, int index, int now_sum) { if (index >= nums.size()) { if (now_sum == S) { count++; } return; } now_sum += nums[index]; index++; help(nums, S, count, index, now_sum); index--; now_sum -= nums[index]; now_sum -= nums[index]; index++; help(nums, S, count, index, now_sum); } class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { if (nums.size() == 0) { return 0; } int count = 0, index = 0, now_sum = 0; help(nums, S, count, index, now_sum); return count; } };
