Thinking about the arrangement problem in the backtracking problem (leetcode questions 46 and 47)

1. Configuration environment

Usage environment ：python3.7
platform ：Windows10
IDE：PyCharm

2. The origin of blog

Bloggers are brushing LeetCode I have a little thought about the full arrangement problem , Record here .

3. Problem description

array 、 The key problem in combinatorial problems is de duplication , The common method is to adopt used Array for de duplication , But this may not be the best way , With LeetCode46 For example

4. Common methods

Take the method provided by the code Capriccio as an example
Method 1 ： use usage_list Array to record , Every time you enter backtracking （backtracking） If yes, you can judge whether to use the modified element , So as to achieve weight removal .

class Solution:
    def __init__(self):
        self.path = []
        self.paths = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        usage_list = [False] * len(nums)
        self.backtracking(nums, usage_list)
        return self.paths

    def backtracking(self, nums: List[int], usage_list: List[bool]) -> None:
        # Base Case Find the leaf node 
        if len(self.path) == len(nums):
            self.paths.append(self.path[:])
            return

        #  Single layer recursive logic 
        for i in range(0, len(nums)):  #  Search from scratch 
            #  If self.path The elements included in , skip 
            if usage_list[i] == True:
                continue
            usage_list[i] = True
            self.path.append(nums[i])
            self.backtracking(nums, usage_list)     #  Vertical transmission of usage information , duplicate removal 
            self.path.pop()
            usage_list[i] = False

Method 2 ： lose usage_list, use self.path Instead of , But the thought of weight removal still lies in judgment num[i] Whether it appears in the record , If so, just continue fall

class Solution:
    def __init__(self):
        self.path = []
        self.paths = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.backtracking(nums)
        return self.paths

    def backtracking(self, nums: List[int]) -> None:
        # Base Case Find the leaf node 
        if len(self.path) == len(nums):
            self.paths.append(self.path[:])
            return

        #  Single layer recursive logic 
        for i in range(0, len(nums)):  #  Search from scratch 
            #  If self.path The elements included in , skip 
            if nums[i] in self.path:
                continue
            self.path.append(nums[i])
            self.backtracking(nums)
            self.path.pop()

5. My thinking

Ideas ：
Whether to use usage_list still self.path It's all about recording element usage through a container , During recursion , Judge all elements once , For the use of elements continue operation .

Perhaps there is a more direct method of weight removal , Enter through control backtracking Of nums Array , Direct pair nums Array for de duplication , Let in backtracking Of nums It has been removed , In the use of for When traversing between layers , You can directly skip the elements being used , The specific operation is as follows ：

# author:Hurricane
# date: 2022/7/2
# E-mail:[email protected]


class Solution:
	def permute(self, nums):
		self.path = []
		self.res = []
		self.backtracking(nums, len(nums))
		return self.res

	def backtracking(self, nums, length):
		if len(self.path) == length:
			self.res.append(self.path[:])
			return

		for i in range(len(nums)):
			self.path.append(nums[i])
			self.backtracking(nums[0:i] + nums[i + 1:], length)
			self.path.pop()

The core code is

self.backtracking(nums[0:i] + nums[i + 1:], length)

This line of code controls the entry backtracking The elements of , Enter directly from backtracking The source of the finished heavy ,

6. Other similar topics

about LeetCode47 Questions can also be carried out with the same idea

Here is also the way bloggers think

# author:Hurricane
# date: 2022/7/2
# E-mail:[email protected]


class Solution:
	def permuteUnique(self, nums):
		self.path = []
		self.res = []
		nums.sort()
		self.backtracking(nums, len(nums))
		return self.res

	def backtracking(self, nums, length):
		if len(self.path) == length:
			self.res.append(self.path[:])
			return

		for i in range(len(nums)):
			if i > 0 and nums[i] == nums[i - 1]:
				continue
			self.path.append(nums[i])
			self.backtracking(nums[0:i] + nums[i + 1:], length)
			self.path.pop()

7. reference

1. Code Capriccio full arrangement
2. Code Capriccio arrangement problem （ Two ）

8. Conclusion

If this article is helpful to you 、 Collect and take away with one click , Your support is my greatest motivation ！(づ｡◕ᴗᴗ◕｡)づ