美文网首页
Java-0011-递归回溯小试牛刀

Java-0011-递归回溯小试牛刀

作者: 云转水流 | 来源:发表于2016-07-22 01:31 被阅读215次

2016.7.22

groupSum

Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? This is a classic backtracking recursion problem. Once you understand the recursive backtracking strategy in this problem, you can use the same pattern for many problems to search a space of choices. Rather than looking at the whole array, our convention is to consider the part of the array starting at index start and continuing to the end of the array. The caller can specify the whole array simply by passing start as 0. No loops are needed -- the recursive calls progress down the array.
groupSum(0, [2, 4, 8], 10) → true
groupSum(0, [2, 4, 8], 14) → true
groupSum(0, [2, 4, 8], 9) → false

public boolean groupSum(int start,int[] nums,int target){
      
}
题意:

给定一个int型数组,你可以选择数组的中的数相加来得到给定的目标数吗?这是一个经典的回溯递归问题。一旦你在这个问题上了解了递归回溯策略,你可以使用相同的模式为许多问题提供一个搜寻空间的解决方法。我们的惯例是考虑从索引开始到结束的数组部分,而不是看整个数组。调用方可以简单地通过从0开始指定整个数组。没有循环是必要的-递归调用的数组的进度。

即,从start索引开始从数组nums中选择若干个数来相加得到一个target的值,能则返回true,不能则返回false。

整个问题的关键:怎么返回分支口并进入另一个分支

思路:
groupSum方法的返回类型是boolean类型,我们可以先加上索引对应的数组数,然后用groupSum将剩下的对应参数传入,并作为if的表达式,这样它返回的就是加过这个数后还能否得到剩下的target。
如果能则返回true;不能则不加这个数,并将索引加1后传入groupSum。
在方法的最前面写判断递归结束的条件和结果。

    public boolean groupSum(int start,int[] nums,int target){
        if(target==0)
              return true;
        if(start==nums.length)
            return false;
        if(groupSum(start+1,nums,target-nums[start])){
            return true;
        }
        else{
            return groupSum(start+1,nums,target);
        }
    }

可能看懂了代码的意思,但还不是很理解它到底是怎么递归怎么回溯的。
下面我做了一个图,帮助大家看懂
图片很大,但显示问题网页上放不了多大,建议下载递归回溯groupSum下来看

递归回溯groupSum500.jpg

思路更清晰的代码(2016.7.30补)

    public boolean groupSum(int start,int[] nums,int target){
        if(target==0)
              return true;
        if(start==nums.length)
            return false;
        return groupSum(start+1,nums,target-nums[start])||groupSum(start+1,nums,target);
    }

相关文章

  • Java-0011-递归回溯小试牛刀

    2016.7.22 groupSum Given an array of ints, is it possible...

  • 8.30 leetcode刷题(2)

    递归和回溯:17 电话号码 思路:运用递归去实现回溯算法的思想。回溯算法本质上是一种暴力搜索,通过递归调用去实现,...

  • LeetCode之回溯算法

    回溯法也可以叫做回溯搜索法,它是一种搜索的方式。回溯是递归的副产品,只要有递归就会有回溯。因为回溯的本质是穷举,穷...

  • 二叉树算法之0-计算二叉树的深度

    算法思想:使用递归 算法解析:分别递归左树和右树,递归到叶子节点时返回0,递归回溯时值+1,不断累积回溯的深度,每...

  • 递归、迭代、回溯、广度和深度优先

    在学习算法的时候,经常碰到递归、迭代、回溯、广度优先和深度优先算法,可是回溯使用了递归,深度优先也使用了递归,广度...

  • 递归,回溯

    什么叫递归:函数在运行时调用自己,这个函数就叫递归函数,调用的过程叫做递归; 递归的特点:1、递归函数必须要有终止...

  • 93. Restore IP Addresses

    基本上DFS就是回溯,回溯就是用递归来实现的;

  • 递归2-回溯与递归

    I. 回溯算法基础 回溯与递归的区别和联系  很多人不理解回溯与递归到底是什么关系。其实很简单,回溯算法是一种算法...

  • 递归(迭代、递归、回溯)

    递归的本质: 是指一种通过重复将问题分解为同类的子问题而解决问题的方法,其核心思想是分治策略。 递归分为两个过程,...

  • 24点问题-Swift

    数学归纳法递归回溯

网友评论

      本文标题:Java-0011-递归回溯小试牛刀

      本文链接:https://www.haomeiwen.com/subject/adfbjttx.html