【代码随想录——回溯算法—

【代码随想录——回溯算法——三周目】

devtools/2024/10/23 12:35:39/

1. 子集2

在这里插入图片描述这题需要先进行排序，和候选人那题类似。防止出现重复的子集。

func subsetsWithDup(nums []int) [][]int {path := make([]int, 0)res := make([][]int, 0)sort.Ints(nums)var dfs func(nums []int, start int)dfs = func(nums []int, start int) {res = append(res, append([]int(nil), path...)) //使用append创建path的副本for i := start; i < len(nums); i++ {if i != start && nums[i] == nums[i-1] {continue}path = append(path, nums[i])dfs(nums, i+1)path = path[:len(path)-1]}}dfs(nums, 0)return res
}

2. 递增子序列

在这里插入图片描述

func findSubsequences(nums []int) [][]int {res := make([][]int,0)path := make([]int,0)var dfs func(nums []int,start int)dfs = func(nums []int,start int){if len(path)>=2{res = append(res,append([]int(nil), path...))}used := make(map[int]bool,len(path))for i:=start;i<len(nums);i++{if used[nums[i]]{//去重continue}if len(path)==0 || nums[i]>=path[len(path)-1]{path = append(path,nums[i])used[nums[i]]=truedfs(nums,i+1)path = path[:len(path)-1]}}}dfs(nums,0)return res
}

3. 全排列

在这里插入图片描述

var (res [][]intpath  []intst    []bool   // state的缩写
)
func permute(nums []int) [][]int {res, path = make([][]int, 0), make([]int, 0, len(nums))st = make([]bool, len(nums))dfs(nums, 0)return res
}func dfs(nums []int, cur int) {if cur == len(nums) {tmp := make([]int, len(path))copy(tmp, path)res = append(res, tmp)}for i := 0; i < len(nums); i++ {if !st[i] {path = append(path, nums[i])st[i] = truedfs(nums, cur + 1)st[i] = falsepath = path[:len(path)-1]}}
}

4. 全排列2

在这里插入图片描述
需要注意：如何去重。先对数组进行排序，对于相同的字母，如果前面没选，则后面的页不能选。

var(path []intres [][]int
)
func permuteUnique(nums []int) [][]int {path = make([]int,0)res = make([][]int,0)used := make([]bool,len(nums))sort.Ints(nums)dfs(nums,used,0)return res
}func dfs(nums []int,used []bool,count int){if count==len(nums){res=append(res,append([]int(nil),path...))}for i:=0;i<len(nums);i++{if i!=0 && nums[i]==nums[i-1] && used[i-1]==false{continue}if used[i]==false{path = append(path,nums[i])used[i]=truedfs(nums,used,count+1)path = path[:len(path)-1]used[i]=false}}
}