回溯法

回溯法

回溯法是暴力搜索法的一种,从直观的角度来看,它是创建了一颗树。但和彻底的暴力法不一样的是,它在求解的过程当中可以对于那些不符合要求的节点及时的剪枝,“回溯”回去。
在创建这颗树的过程中,控制好递归当中循环的细节、退出的条件、添加哪些节点的值是相当重要的。不一样的方法获得的树不一样,结果也不一样。python

下面是一些leetcode的题目,能够帮助更好的理解回溯法。数组

leetcode22: 括号生成

给出 n 表明生成括号的对数,请你写出一个函数,使其可以生成全部可能的而且有效的括号组合。app

例如,给出 n = 3,生成结果为:函数

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]3d

代码以下:code

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        results = []
        self.generate_helper(results, '', 0, 0, n)
        return results

    def generate_helper(self, results, str, open, close, max):
        if len(str) == 2 * max:
            results.append(str)
            return

        if open < max:
            self.generate_helper(results, str+'(', open+1, close, max)
        if close < open:
            self.generate_helper(results, str+')', open, close+1, max)

图片描述:
对象

分析:递归的时候左括号老是在右括号前面,并且右括号的数量不得多于左括号,递归结束的条件是括号长度等于预约的长度。blog


leetcode39 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中全部可使数字和为 target 的组合。candidates 中的数字能够无限制重复被选取。递归

说明:
全部数字(包括 target)都是正整数。
解集不能包含重复的组合。图片

示例1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

代码以下:

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        results = []
        candidates.sort()
        self.dfs(candidates, target, 0, [], results)
        return results
    def dfs(self, candidates, target, index, result, results):
        if target < 0:
            return
        if target == 0:
            results.append(result)
            return
        for i in range(index, len(candidates)):
            self.dfs(candidates, target-candidates[i], i,result+[candidates[i]], results)
            # 在这里使用result+[candidates[i]],而不是使用append。
            # +产生了一个新的对象,而append是在原有的对象上面进行更新。
            # 若是要使用append,那么当这一步运行完之后,还须要把添加的值pop出来(至关于回溯),
            # 另外程序16行要修改成results.append(result.copy())。
            # 个人程序均使用第一种方法。

图片描述:

分析:树的左侧节点值明显要比右侧节点值多,也就是树向左偏,这是由递归过程当中的for循环来决定的,确切的是由传入的i的值决定的。


leetcode40 组合总和II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中全部可使数字和为 target 的组合。candidates 中的每一个数字在每一个组合中只能使用一次。

说明:
全部数字(包括目标数)都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1,7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

代码以下:

class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        results = []
        self.dfs(candidates, target, 0, [], results)
        return results

    def dfs(self, candidates, target, index, result, results):
        if target <0:
            return
        if target == 0:
            results.append(result)
            return
        for i in range(index, len(candidates)):
            if i > index and candidates[i] == candidates[i-1]:
                continue
            self.dfs(candidates, target-candidates[i], i+1, result+[candidates[i]], results)

图片描述:

分析:能够看出和上一题相比,在递归循环的里面有两个不一样,第一个不一样是:使用continue来处理重复值的状况,当第二次出现的值和第一次出现的值相同的时候,因为在第一次已经处理过了,全部之后会直接跳过。另一点不一样的是递归传入的值由i变成了i+1,这能够在两张图里面看出来,好比第一张图2下面的节点是2,3,6,7,而第二张图的节点是3,6,7,是由于i的值多增长一位的缘故。


leetcode 46:全排列

给定一个没有重复数字的序列,返回其全部可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

代码以下:

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        results = []
        self.dfs(nums, [], results)
        return results
    
    def dfs(self, nums, result, results):
        if len(nums) == 0:
            results.append(result)
            return
        for i in range(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], result+[nums[i]], results)

图片描述:

分析:树的左侧节点和右侧节点的值同样多,保存的是树的叶子节点的值。


leetcode47: 全排列(II)

给定一个可包含重复数字的序列,返回全部不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

代码以下:

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        results = []
        nums.sort()
        self.dfs(nums, [], results)
        return results

    def dfs(self, nums, result, results):
        if len(nums) == 0:
            results.append(result)
            return
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[:i]+nums[i+1:], result+[nums[i]], results)

leetcode78 子集

给定一组不含重复元素的整数数组 nums,返回该数组全部可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

代码:

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        results = []
        self.dfs(nums, 0, [], results)
        return results
        
    def dfs(self, nums, index, result, results):
        if index == len(nums):
            results.append(result)
            return
        results.append(result)
        for i in range(index, len(nums)):
            self.dfs(nums, i+1, result+[nums[i]], results)

图片描述:

分析:在这道题当中,results当中保存全部节点的值,而不单单是叶子节点的值。


leetcode90 子集II

给定一个可能包含重复元素的整数数组 nums,返回该数组全部可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

代码以下:

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        results = []
        self.dfs(nums, 0, [], results)
        return results
        
    def dfs(self, nums, index, result, results):
        if index == len(nums):
            results.append(result)
            return
        results.append(result)
        for i in range(index, len(nums)):
            if i > index and nums[i] == nums[i-1]:
                continue
            self.dfs(nums, i+1, result+[nums[i]], results)

分析:和上一道题不一样之处在于使用continue机制来处理重复的值。

相关文章
相关标签/搜索