代码随想录算法训练营第二十五天 | 491、46、47

算法
, , ,

491. 递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package main

func findSubsequences(nums []int) [][]int {
    var result [][]int
    var backtrack func(int, []int)

    backtrack = func(start int, path []int) {
        if len(path) >= 2 {
            tmp := make([]int, len(path))
            copy(tmp, path)
            result = append(result, tmp)
        }

        used := make(map[int]bool) // 用于记录当前层使用过的元素
        for i := start; i < len(nums); i++ {
            // 当前元素已被使用过，或者不满足递增条件时跳过
            if used[nums[i]] || (len(path) > 0 && nums[i] < path[len(path)-1]) {
                continue
            }
            used[nums[i]] = true // 标记当前元素已使用
            backtrack(i+1, append(path, nums[i]))
        }
    }

    backtrack(0, []int{})
    return result
}

46. 全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

func permute(nums []int) [][]int {
    var result [][]int
    var backtrack func(int)

    backtrack = func(first int) {
        if first == len(nums) {
            tmp := make([]int, len(nums))
            copy(tmp, nums)
            result = append(result, tmp)
            return
        }
        for i := first; i < len(nums); i++ {
            nums[first], nums[i] = nums[i], nums[first] // 交换元素位置
            backtrack(first + 1)                        // 递归处理下一个位置
            nums[first], nums[i] = nums[i], nums[first] // 回溯，恢复原数组
        }
    }

    backtrack(0)
    return result
}

47. 全排列 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package main

import "sort"

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums) // 先排序以便处理重复元素
    var result [][]int
    var backtrack func(int)

    backtrack = func(first int) {
        if first == len(nums) {
            // 复制当前排列到结果集
            tmp := make([]int, len(nums))
            copy(tmp, nums)
            result = append(result, tmp)
            return
        }
        used := make(map[int]bool) // 记录当前层已使用的元素

        for i := first; i < len(nums); i++ {
            // 跳过同一层已使用过的相同元素
            if used[nums[i]] {
                continue
            }
            used[nums[i]] = true

            // 将 nums[i] 交换到 first 位置
            nums[first], nums[i] = nums[i], nums[first]
            // 递归处理下一个位置
            backtrack(first + 1)
            // 回溯，恢复交换前的状态
            nums[first], nums[i] = nums[i], nums[first]
        }
    }

    backtrack(0)
    return result
}