题目：491. 递增子序列
思路：
核心问题——同层去重，这一题不能够重新排序因此不可以用i > index && nums[i] == nums[i-1]来去重，而是每一层开一个map来判断该数是否出现过
代码：
var (
res [][]int
path []int
)
func findSubsequences(nums []int) [][]int {
res = make([][]int, 0)
path = make([]int, 0, len(nums))
FindSubsequences(nums, 0)
return res
}
func FindSubsequences(nums []int, index int) {
if len(path) >= 2 { // 只要长度大于等于2就可以添加
res = append(res, append([]int{},path...))
}
isExist := make(map[int]bool) // 同层去重
for i := index; i < len(nums); i++ {
if isExist[nums[i]] == true {
continue
}
lens := len(path)
if lens == 0 || nums[i] >= path[lens-1] { // 如果path没有数或者最后一个数小于等于当前就递归
path = append(path, nums[i])
isExist[nums[i]] = true
FindSubsequences(nums, i + 1)
path = path[:lens]
}
}
}
参考：
题目：46. 全排列
思路：
全排列的used数组就是用来保证同一分支下不会多次使用同一个元素
代码：
var (
res [][]int
path []int
used []bool
)
func permute(nums []int) [][]int {
res = make([][]int, 0)
path = make([]int, 0, len(nums))
used = make([]bool, len(nums))
Permute(nums)
return res
}
func Permute(nums []int) {
if len(path) == len(nums) { // 排列完成
res = append(res, append([]int{},path...))
return
}
for i, ok := range used { // 直接遍历used
if ok { // 如果已经被使用过了
continue
}
used[i] = true // 标记
path = append(path, nums[i])
Permute(nums)
path = path[:len(path)-1]
used[i] = false // 取消标记
}
return
}
参考：
题目：47. 全排列 II
思路：
有重复的全排列，used身兼数职，首先要用来判断同层不会重复i > 0 && nums[i] == nums[i-1] && used[i-1] == false .
还要判断同枝没有复用!ok
代码：
var (
res [][]int
path []int
used []bool
)
func permuteUnique(nums []int) [][]int {
res = make([][]int, 0)
path = make([]int, 0, len(nums))
used = make([]bool, len(nums))
sort.Ints(nums)
PermuteUnique(nums)
return res
}
func PermuteUnique(nums []int) {
if len(nums) == len(path) {
res = append(res, append([]int{},path...))
return
}
for i, ok := range used {
if i > 0 && nums[i] == nums[i-1] && used[i-1] == false {
continue
}
if !ok {
used[i] = true
path = append(path,nums[i])
PermuteUnique(nums)
path = path[:len(path)-1]
used[i] = false
}
}
}