LeetCode刷题--- 目标和

二、设计代码

（1）全局变量

int sum;
int ret;

• sum（target的值）?
• ret（记录符合target 值的次数）

（2）设计递归函数

void dfs(vector<int>& nums, int pos, int path);

• 参数：nums（数组），pos（当前要处理的元素下标），path（当前状态和）；
• 返回值：无；
• 函数作?：查找所有值为 target 的次数；

1. 递归结束条件：pos?与数组?度相等，判断当前状态的 path?是否与?标值（target）相等，若是计数（ret）加?；
2. 选择当前元素进?加操作，递归下?个位置，并更新参数 path；
3. 选择当前元素进?减操作，递归下?个位置，并更新参数 path；

以上思路讲解完毕，大家可以自己做一下了

代码实现

时间复杂度：O()，其中 n?是数组 nums 的长度。回溯需要遍历所有不同的表达式，共有 ?种不同的表达式，每种表达式计算结果需要 O(1) 的时间，因此总时间复杂度是 O()。

空间复杂度：O(n)，其中 n?是数组 nums 的长度。空间复杂度主要取决于递归调用的栈空间，栈的深度不超过 n。

class Solution 
{
public:
    int sum;
    int ret;

    void dfs(vector<int>& nums, int pos, int path)
    {
	    if (pos == nums.size())
	    {
		    if (path == sum)
		    {
			    ret++;
		    }
		    return;
	    }

	    dfs(nums, pos + 1, path + nums[pos]);

	    dfs(nums, pos + 1, path - nums[pos]);
    }
    int findTargetSumWays(vector<int>& nums, int target)
    {
        sum = target;

        dfs(nums, 0, 0);

        return ret;
    }
};