回溯法

Posted on |

Leetcode题目

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}

        def backtrack(combination, next_digits):
            # if there is no more digits to check
            if len(next_digits) == 0:
                # the combination is done
                output.append(combination)
            # if there are still digits to check
            else:
                # iterate over all letters which map
                # the next available digit
                for letter in phone[next_digits[0]]:
                    # append the current letter to the combination
                    # and proceed to the next digits
                    backtrack(combination + letter, next_digits[1:])

        output = []
        if digits:
            backtrack("", digits)
        return output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}


        def dfs(combination,index):
            if len(combination)==len(digits):
                output.append(combination)
                return

            for letter in phone[digits[index]]:
                dfs(combination+letter,index+1)

        output=[]
        if digits:
            dfs('',0)
        return output

46.全排列

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

1
2
3
4
5
6
7
8
9
10
11
示例:
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        self.backtrack(nums, res, [])
        return res

    def backtrack(self, nums, res, temp):
        if len(temp)==len(nums):      # quit loop 回溯条件
            res.append(list(temp))
        else:
            for n in nums:
                if n in temp:         # cut duplicate
                    continue          # 如果在当前排列中已经有n了，就continue，相当于分支限界，即不对当前节点子树搜寻了
                temp.append(n)
                self.backtrack(nums, res, temp)
                temp.pop()            # 把结尾的元素用nums中的下一个值替换掉，遍历下一颗子树

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res=[]
        self.helper(nums,0,len(nums))
        return self.res

    def helper(self,nums,position,end):
        if position==end:
            self.res.append(list(nums))
        else:
            for i in range(position,end):
                nums[i],nums[position]=nums[position],nums[i]
                self.helper(nums,position+1,end)
                nums[i],nums[position]=nums[position],nums[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        self.dfs(nums, res, [])
        return res
    def dfs(self, nums, res, path):
        if not nums:
            res.append(path)
        else:
            for i, n in enumerate(nums):
                self.dfs(nums[:i]+nums[i+1:], res, path+[n])

47.全排列II

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

1
2
3
4
5
6
7
8
示例:
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums=sorted(nums)
        res=[]
        used=[False for _ in range(len(nums))]
        self.backtrack(nums,res,used,[])
        return res

    def backtrack(self,nums,res,used,tmp):
        if len(tmp)==len(nums):
            res.append(list(tmp))
            return
        for i in range(len(nums)):
            if used[i] or i>0 and nums[i]==nums[i-1] and not used[i-1]:
                continue
            tmp.append(nums[i])
            used[i]=True
            self.backtrack(nums,res,used,tmp)
            used[i]=False
            tmp.pop()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import Counter
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res,counter,n=[],Counter(nums),len(nums)
        self.backtrack(list(set(nums)), res, [], counter, n)
        return res

    def backtrack(self, nums, res, temp, counter, length):
        if len(temp)==length:     # 回溯点
            res.append(list(temp))
            return
        for n in nums:            # 横向遍历
            if counter[n]==0:     # 分支限界
                continue

            temp.append(n)
            counter[n]-=1
            self.backtrack(nums, res, temp, counter, length)    # 纵向遍历
            temp.pop()
            counter[n]+=1

78.子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
示例:
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans=[]
        self.backtrack(nums,ans,[],0)
        return ans

    def backtrack(self,nums,ans,tmp,start):
        ans.append(list(tmp))
        for i in range(start,len(nums)):
            tmp.append(nums[i])
            self.backtrack(nums,ans,tmp,i+1)
            tmp.pop()
# backtrack([1, 2, 3], [], [], 0)
# backtrack([1, 2, 3], [[]], [1], 1)
# backtrack([1, 2, 3], [[], [1]], [1, 2], 2)
# backtrack([1, 2, 3], [[], [1], [1, 2]], [1, 2, 3], 3)
# --------------------
# pop:  3
# --------------------
# pop:  2
# backtrack([1, 2, 3], [[], [1], [1, 2], [1, 2, 3]], [1, 3], 3)
# --------------------
# pop:  3
# --------------------
# pop:  1
# backtrack([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3]], [2], 2)
# backtrack([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]], [2, 3], 3)
# --------------------
# pop:  3
# --------------------
# pop:  2
# backtrack([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]], [3], 3)
# --------------------
# pop:  3
# --------------------
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

90.子集II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

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

1
2
3
4
5
6
7
8
9
10
11
示例:
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        nums=sorted(nums)
        self.backtrack(nums,res,[],0)
        return res

    def backtrack(self,nums,res,temp,start):
        res.append(list(temp))
        for i in range(start,len(nums)):
            if i>start and nums[i]==nums[i-1]:    # skip duplicates
                continue
            temp.append(nums[i])
            self.backtrack(nums,res,temp,i+1)
            temp.pop()
# backtrack([1, 2, 2], [], [], 0)
# backtrack([1, 2, 2], [[]], [1], 1)
# backtrack([1, 2, 2], [[], [1]], [1, 2], 2)
# backtrack([1, 2, 2], [[], [1], [1, 2]], [1, 2, 2], 3)
# pop:  2
# --------------------
# pop:  2
# --------------------
# pop:  1
# --------------------
# backtrack([1, 2, 2], [[], [1], [1, 2], [1, 2, 2]], [2], 2)
# backtrack([1, 2, 2], [[], [1], [1, 2], [1, 2, 2], [2]], [2, 2], 3)
# pop:  2
# --------------------
# pop:  2
# --------------------
# [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

39.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 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]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res=[]
        self.backtrack(candidates,target,res,[],0)
        return res

    def backtrack(self,candidates,target,res,temp,start):
        if target<0:
            return
        elif target==0:
            res.append(list(temp))
        else:
            for i in range(start,len(candidates)):
                temp.append(candidates[i])
                self.backtrack(candidates,target-candidates[i],res,temp,i)    # 元素可以重复使用，所以此处是i，不是i+1
                temp.pop()

40.组合总和II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 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]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res=[]
        used=set()

        def dfs(temp, start, target):
            if target==0:
                res.append(list(temp))
                return
            for i in range(start, len(candidates)):
                if i> start and candidates[i]==candidates[i-1]:
                    continue
                if i not in used and target-candidates[i]>=0:
                    temp.append(candidates[i])
                    used.add(i)
                    dfs(temp, i+1, target-candidates[i])
                    temp.pop()
                    used.discard(i)

        candidates.sort()
        dfs([], 0, target)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        def combine(candidates, target, p, ans):
            if target == 0:
                ans.append(p)
                return

            for i, c in enumerate(candidates):
                if i > 0 and c == candidates[i-1]:
                    continue
                if target - c < 0:
                    break
                combine(candidates[i+1:], target - c, p + [c], ans)
        ans = []
        candidates.sort()
        combine(candidates, target, [], ans)
        return ans

216.组合总和III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：

所有数字都是正整数。
解集不能包含重复的组合。

1
2
3
4
5
6
7
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        res=[]
        self.backtrack(k, n, res, [], 1)
        return res

    def backtrack(self, k, target, res, temp, start):
        if len(temp)>k:
            return
        elif len(temp)==k and target==0:
            res.append(list(temp))
        else:
            for i in range(start,10):
                temp.append(i)
                self.backtrack(k, target-i, res, temp, i+1)
                temp.pop()

22.括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

n 
1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n < 1:
            return []
        res = []
        self.backtracking(n, res, "", 0, 0)
        return res
    def backtracking(self,n, res, temp, left, right):
        if left < n:
            self.backtracking(n, res, temp + '(' , left+1, right)
        if right < left:
            self.backtracking(n ,res, temp + ')', left, right+1)
        if right == n:
            res.append(temp)

资料