leetcode494-目标和

原题

给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:
-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
一共有5种方法让最终目标和为3。

注意:

  1. 数组非空,且长度不会超过20。
  2. 初始的数组的和不会超过1000。
  3. 保证返回的最终结果能被32位整数存下。

解法

思想

DFS比较暴力,追求时间快可以用01背包问题的动态规划思想,以后更。

代码

class Solution {
    public int[] numsArray;
    public int target;
    public int findTargetSumWays(int[] nums, int S) {
        numsArray = nums;
        target = S;
        return dfs(0,0);
    }
    public int dfs(int index,int sum){
        if(index == numsArray.length){
            if(sum == target) return 1;
            else return 0;
        }
        return dfs(index+1,sum+numsArray[index])+dfs(index+1,sum-numsArray[index]);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode494-%e7%9b%ae%e6%a0%87%e5%92%8c/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月11日
下一篇 2019年12月13日

相关推荐

  • leetcode224-基本计算器

    原题 实现一个基本的计算器来计算一个简单的字符串表达式的值。 字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格 。 示例1: 输入: "1 + 1…

    算法 2020年1月26日
    0130
  • 剑指offer06-从尾到头打印链表

    原题(来源Leetcode) 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 示例1: 输入: head = [1,3,2] 输出: [2,3,1] 限制: …

    算法 2020年4月10日
    050
  • leetcode485-最大连续1的个数

    原题 给定一个二进制数组, 计算其中最大连续1的个数。 示例 1: 输入: [1,1,0,1,1,1] 输出: 3 解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是…

    算法 2019年11月20日
    0120
  • leetcode169-多数元素

    原题 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例1:…

    算法 2020年2月5日
    070
  • leetcode560-和为K的子数组

    原题 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 , [1,1]…

    算法 2020年5月15日
    0460
  • leetcode1014-最佳观光组合

    原题 给定正整数数组 A,A[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的距离为 j - i。 一对景点(i < j)组成的观光组合的得分为(A[i]…

    算法 2020年6月17日
    01900
  • leetcode297-二叉树的序列化与反序列化

    原题 序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。…

    算法 2020年1月15日
    0100
  • 海量数据去重-由BitMap引出的布隆过滤器

    本文参考资源: 那些惊艳的算法们(一)——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客 详解布隆过滤器的原理、使用场景和注意事项 - 简书 概述 昨天…

    2020年2月28日
    01.3K0
  • leetcode378-有序矩阵中第K小的元素

    原题 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ &nbs…

    算法 2020年2月14日
    0420
  • leetcode42-接雨水

    原题 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高…

    2020年1月23日
    0290

发表回复

登录后才能评论