回溯组合排列生成 LeetCode

╰半橙微兮° 2022-10-29 04:26 203阅读 0赞

# 回溯 组合 排列 生成 算法题目 #

## [77. 组合][77.] ##

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

**示例:**

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

**解法1:** 回溯 递归

class Solution:
        def combine(self, n: int, k: int) -> List[List[int]]:
            if k > n:
                return []
            if k == n:  # 可以减少运行时间
                return [list(range(1, n+1))]
            # 回溯
            result = []
            def huisu(start, temp):
                if len(temp) == k:
                    result.append(temp.copy()) # 特别小心，必须使用copy(浅copy)) 或 深copy
                    return 
                for i in range(start, n+1):
                    temp.append(i)  # 回溯
                    huisu(i+1, temp)  
                    temp.pop()
                return 
            huisu(1, [])
            return result

## [39. 组合总和][39.] ##

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

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

**说明：**

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

**示例 1：**

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

**解法1:** 回溯 递归

class Solution:
        def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
            result = []
            def digui(target, target_list):
                for item in candidates:
                    if target - item == 0:  # 可以相等记录下来
                        tem = target_list+[item]
                        if sorted(tem) not in result:  # 去重复 
                            result.append(sorted(tem))
                    elif target - item > 0:
                        digui(target-item, target_list+[item]) # 传参时， 不要加进去
                    else:
                        pass
            digui(target, [])
            return result

## [46. 全排列][46.] ##

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

**示例:**

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

**解法1:** 递归

class Solution:
        def permute(self, nums: List[int]) -> List[List[int]]:
            # global out
            
            def digui(numlist, S=[]):
                if len(S) == n:
                    out.append(S)
                    return 
                for i in range(len(numlist)): # 递归+回溯
                    digui(numlist[:i] + numlist[i+1:], S+[numlist[i]])
                return 
            out = []
            n = len(nums)
            digui(nums, [])
            return out

## [全排列 II][II] ##

给定一个可包含重复数字的序列 nums ，**按任意顺序** 返回所有不重复的全排列。

**示例 1：**

输入：nums = [1,1,2]
    输出：
    [[1,1,2],
     [1,2,1],
     [2,1,1]]

**解法1:** 全排列 + 去重复； 968ms

class Solution:
        def permuteUnique(self, nums: List[int]) -> List[List[int]]:
            def digui(numlist, S=[]):
                if len(S) == n:
                    if S not in out:  # 去重复，费时
                        out.append(S)
                    return 
                for i in range(len(numlist)): # 递归+回溯
                    digui(numlist[:i] + numlist[i+1:], S+[numlist[i]])
                return 
            out = []
            n = len(nums)
            digui(nums, [])
            return out

**解法2:** 排序 + 递归 + 去重复； 52 ms

class Solution:
        def permuteUnique(self, nums: List[int]) -> List[List[int]]:
            nums.sort() # 加一次排序
            n = len(nums)
            res = []
            def digui(nums, temp):
                if len(temp) == n:
                    res.append(temp) # 没加copy，因为temp不是直接传递过来的；
                    return 
                for i in range(len(nums)):
                    if i+1 < len(nums) and nums[i] == nums[i+1]: # 去重复
                        continue
                    digui(nums[:i]+nums[i+1:], temp + [nums[i]])
            
            digui(nums, [])
            return res

## [31. 下一个排列][31.] \*\* ##

实现获取 **下一个排列** 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。  
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。  
必须 `原地` 修改，只允许使用额外常数空间。

[优秀题解][Link 1]

**示例 1：**

输入：nums = [1,2,3,4,6,5]
    输出：[1,2,3,5,4,6]

**解法1:**

123456
    123465
    123546
    ...
    654321

class Solution:
        def nextPermutation(self, nums: List[int]) -> None:
            """ Do not return anything, modify nums in-place instead. """
            # “下一个排列”的定义是：给定数字序列的字典序中下一个更大的排列。
            # 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 
            i = len(nums) - 2
            while 0 <= i and nums[i] >= nums[i+1]:  # 找到 第一个nums[i] < nums[i+1]
                i = i - 1
            if i >= 0:
                j = len(nums) - 1
                while j >= 0 and nums[i] >= nums[j]: # 最靠右的大于nums[i]
                    j = j - 1
                nums[i], nums[j] = nums[j], nums[i] # 互换
        
            left = i + 1
            right = len(nums) - 1
            while left < right:  # 左右互换, 因为i右边是降序排列了，互换后就是升序；
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
            
            return nums

## [267. 回文排列 II][267. _ II] ##

给定一个字符串 `s` ，返回其通过重新排列组合后所有可能的回文字符串，并去除重复的组合。

如不能形成任何回文排列时，则返回一个空列表。

**示例 1：**

输入: "aabb"
    输出: ["abba", "baab"]

**示例 2：**

输入: "abc"
    输出: []

**解法1:**

class Solution:
        def generatePalindromes(self, s: str) -> List[str]:
            # 1. 要生成 所有 可能的 回文字符串, 判断是否为回文串，超时
            # 2. 判断是否可以构成， 若可以， 使用一半元素，生成所有不重复排列，反转；奇数字符放中间； 可行
            s_dict = { }
            for item in s:
                if item not in s_dict:
                    s_dict[item] = 1
                else:
                    s_dict[item] += 1
            # print(s_dict)
            odd_count = 0  # 统计奇数字符个数
            odd_str = ""  # 记录是哪个奇数字符
            new_s_dict = { }
            for k, v in s_dict.items():
                if v % 2 != 0:
                    odd_count += 1
                    if odd_count > 1:
                        return []
                    else:
                        new_s_dict[k] =  (v-1) // 2
                        odd_str = k
                else:
                    new_s_dict[k] = v // 2
            # 使用一半字母 生成所有可能的 情况
            proce_str = "" 
            for k, v in new_s_dict.items():
                proce_str += k*v
            # print(proce_str)
            # print(odd_str)
            res_temp = []
            n = len(proce_str)
            def digui(strs, temp=""): # 生成所有可能的排列
                if len(temp) == n:
                    res_temp.append(temp)
                    return 
                for i in range(len(strs)):
                    if i+1<len(strs) and strs[i]==strs[i+1]:
                        continue
                    digui(strs[:i]+strs[i+1:], temp+strs[i])
                return 
            digui(proce_str, "")  
            # print(res_temp)
            new_res = []
            for item in res_temp: # 每种可能+奇数字符+每种可能的倒序
                new_res.append(item+odd_str+item[::-1])
            return new_res

[77.]: https://leetcode-cn.com/problems/combinations/
[39.]: https://leetcode-cn.com/problems/combination-sum/
[46.]: https://leetcode-cn.com/problems/permutations/
[II]: https://leetcode-cn.com/problems/permutations-ii/
[31.]: https://leetcode-cn.com/problems/next-permutation/
[Link 1]: https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
[267. _ II]: https://leetcode-cn.com/problems/palindrome-permutation-ii/