0、 Preface

This blog is to buckle 494. Objectives and topic , The difficulty of the topic is medium , Can be said to be DFS The exercises of , I little interesting ~

1、 Title Description

2、 Their thinking

2.1 Method 1 ~ utilize DFS

2.1.1 Ideas

Array nums You can add symbols to every element of the + or -, So each element has 2 A way to add symbols ,n Total number 2^n A way to add symbols . Then you can give n After adding symbols to all elements , Make a simple summation , If the result is equal to the target number target, Then the expression is the expression that meets the requirements .

2.1.2 Program code

class Solution {
    
public:
	// DFS  How to write it 1
	/*int findTargetSumWays(vector<int>& nums, int target) { return dfs(nums, target, 0); } int dfs(vector<int> &nums, int target, int left) { if (target == 0 && left == nums.size()) return 1; if (left >= nums.size()) return 0; int ans = 0; ans += dfs(nums, target - nums[left], left + 1); ans += dfs(nums, target + nums[left], left + 1); return ans; }*/

	// DFS  How to write it 2
	int num = 0;
	int findTargetSumWays(vector<int>& nums, int target) {
    
		getNum(nums, target, 0, 0);
		return num;
	}
	void getNum(vector<int>& nums, int target, int index, int sum)
	{
    
		if (index == nums.size())
		{
    
			if (sum == target)
			{
    
				num++;
			}
		}
		else
		{
    
			getNum(nums, target, index + 1, sum + nums[index]);
			getNum(nums, target, index + 1, sum - nums[index]);
		}
	}
};

2.2 Other methods

There are other ways to solve this problem , Such as dynamic return , There is time for follow-up. Continue to add ！