首页 > 其他 > 详细

494. Target Sum 494.目标总和

时间:2020-07-25 20:25:46      阅读:45      评论:0      收藏:0      [点我收藏+]

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.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

思路:试试回溯:
dfs(int[] nums, int S, )
数量不知道该放在哪里
其实为了凑出来一个和,参数里有个pos, 然后sum + nums[pos]就行了

 

return ; //position到头之后,无论如何都要退出一下

 

两个DFS都进行就行:

dfs(nums, pos + 1, currentSum + nums[pos], S);
dfs(nums, pos + 1, currentSum - nums[pos], S);

 

技术分享图片
class Solution {
    int count;
    
    public int findTargetSumWays(int[] nums, int S) {
        //cc
        if (nums == null || nums.length == 0)
            count = 0;
        
        //dfs
        dfs(nums, 0, 0, S);
        
        return count;
    }
    
    public void dfs(int[] nums, int pos, int currentSum, int S) {
        //exit
        if (pos == nums.length) {
            if (currentSum == S) 
                count++;
            return ; //无论如何都要退出一下
        }
        
        dfs(nums, pos + 1, currentSum + nums[pos], S);
        dfs(nums, pos + 1, currentSum - nums[pos], S);
    }
}
View Code

 


 

494. Target Sum 494.目标总和

原文:https://www.cnblogs.com/immiao0319/p/13375960.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!