Leetcode backtracking method

q22 Bracket generation

Subject portal

Answer key

Let's solve this problem in a different way , The topic requires to use n Arrange brackets , We are from 2 * n Choose between the brackets to arrange them from left to right . At this time, we found out , We have chosen more left parentheses than right parentheses , such as "((("、"(()"、"(())“ Such a situation is allowed , however ”())" Such a situation cannot happen . So we made such a strategy at the beginning ：

1. As long as the left bracket always has , Then you can always choose the left bracket
2. As long as the number of left parentheses is greater than the number of right parentheses , We can choose the right bracket
3. When the number of parentheses equals 2 * n, Indicates that an arrangement has been obtained

func generateParenthesis(n int) []string {
    
	res := []string{
    }

	var dfs func(lBracket int, rBracket int, path string)
	dfs = func(lBracket int, rBracket int, path string){
    
		if len(path) >= 2 * n {
    
			res = append(res, path)
			return
		}
		if lBracket > 0 {
    
			dfs(lBracket - 1, rBracket, path + "(")
		}
		if rBracket > lBracket {
    
			dfs(lBracket, rBracket - 1, path + ")")
		}
	}
	dfs(n, n, "")
	return res
}

q40 Combinatorial summation 2

Subject portal

Answer key

This problem uses dfs To solve , First, clarify the situation of reaching the leaf node , Is that when target Be reduced to 0 When , Then go through candidates The subscript , To create a new branch , And subscript as dfs Function parameters to pass parameters . At the same time, weight removal and pruning are needed , When the present candidates When the element of is the same as the previous element , Just skip this loop ; When the currently traversed element ratio target When I was young , Because the array has been ordered , So direct return that will do , Finally, continue recursion along this node .

func combinationSum2(candidates []int, target int) [][]int {
    
	sort.Ints(candidates)
	var res [][]int
	dfs(candidates, nil, target, 0, &res)
	return res
}

func dfs(candidates []int, nums []int, target int, left int, res *[][]int) {
    
	//  Recursive export 
	if target == 0 {
    
		tmp := make([]int, len(nums))
		copy(tmp, nums)
		*res = append(*res, tmp)
		return
	}
	for i := left; i < len(candidates); i++ {
    
		if i != left && candidates[i] == candidates[i - 1] {
     //  duplicate removal 
			continue
		}
		if target < candidates[i] {
      //  prune 
			return
		}
		//  Direct transmission append(nums, candidates[i]) In fact, it includes the backtracking operation ,nums The array has not been changed 
		dfs(candidates, append(nums, candidates[i]), target - candidates[i], i + 1, res)
	}
}

q46 Full Permutation

Subject portal

Answer key

This problem uses dfs To solve , The condition for judging leaf nodes is cur The length of the array and nums The length is the same , At this time cur Array add res Array . Then traverse nums Array to select numbers , To create a new branch , Inside a loop, you need to traverse cur Array , See if the selected number repeats , No problem, just continue along this branch .

func permute(nums []int) [][]int {
    
	var res [][]int
	dfs(nums, []int{
    }, &res)
	return res
}

func dfs(nums []int, cur []int, res *[][]int)  {
    
	if len(nums) == len(cur) {
    
		tmp := make([]int, len(cur))
		copy(tmp, cur)
		*res = append(*res, tmp)
		return
	}
	for i := 0; i < len(nums); i++ {
    
		exist := false
		for j := 0; j < len(cur); j++ {
    
			if nums[i] == cur[j] {
    
				exist = true
				break
			}
		}
		if exist == true {
    
			continue
		}
		dfs(nums, append(cur, nums[i]), res)
	}
}