13.2 集合的组合排列

13.2.1 问题79: 所有子集

LCR 079. 子集

给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

13.2.1.1 分析&题解

使用回溯法, 集合中有n个元素, 时间复杂度: $O(2^n)$

func subsets(nums []int) [][]int {
    res := [][]int{}
    if len(nums) == 0 {
        return res
    }

    helper(nums, 0, &[]int{}, &res)
    
    return res
}

func helper(nums []int, idx int, subset *[]int, res *[][]int) {
    if idx == len(nums) {
        tmp := make([]int, len(*subset))
        copy(tmp, *subset)
        *res = append(*res, tmp)
    } else {
        // 不添加元素
        helper(nums, idx+1, subset, res)

        // 添加元素
        *subset = append(*subset, nums[idx])
        helper(nums, idx+1, subset, res)
        // 回溯
        *subset = (*subset)[:len(*subset)-1]
    }
}

13.2.2 问题80: 包含k个元素的组合

LCR 080. 组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例 1:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2:

输入: n = 1, k = 1
输出: [[1]]

提示:

• 1 <= n <= 20
• 1 <= k <= n

13.2.2.1 分析&题解

func combine(n int, k int) [][]int {
    res := [][]int{}
    helper(n, k, 1, &[]int{}, &res)
    return res
}

func helper(n, k, idx int, com *[]int, res *[][]int) {
    if len(*com) == k {
        tmp := make([]int, len(*com))
        copy(tmp, *com)
        *res = append(*res, tmp)
    } else if idx <= n {
        // 不添加
        helper(n, k, idx+1, com, res)

        // 添加一个数字
        *com = append(*com, idx)
        helper(n, k, idx+1, com, res)
        // 回溯 
        *com = (*com)[:len(*com)-1]
    }
}

13.2.3 问题81: 允许重复元素的组合

LCR 081. 组合总和

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

示例 4：

输入: candidates = [1], target = 1
输出: [[1]]

示例 5：

输入: candidates = [1], target = 2
输出: [[1,1]]

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每个元素都是独一无二的。
• 1 <= target <= 500

13.2.3.1 分析&题解

func combinationSum(candidates []int, target int) [][]int {
    res := [][]int{}
    helper(candidates, target, 0, &[]int{}, &res)
    return res
}

func helper(nums []int, target, idx int, com *[]int, res *[][]int) {
    if target == 0 {
        tmp := make([]int, len(*com))
        copy(tmp, *com)
        *res = append(*res, tmp)
    } else if idx < len(nums) && target > 0 {
        // 不添加数字
        helper(nums, target, idx+1, com, res)
        
        // 添加数字
        *com = append(*com, nums[idx])
        // 数字可复用
        helper(nums, target-nums[idx], idx, com, res)
        // 回溯
        *com = (*com)[:len(*com)-1]
    }
}

13.2.4 问题82: 包含重复元素集合的组合

LCR 082. 组合总和 II

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

13.2.4.1 分析&题解

输入集合中有重复数字, 但是输出中不能有重复的组合, 那么就需要跳过重复的数字.

先将数组排序, 这样就方便跳过重复的数字.

func combinationSum2(candidates []int, target int) [][]int {
    // sort
    sort.Slice(candidates, func(i, j int) bool {
        return candidates[i] < candidates[j]
    })

    res := [][]int{}
    helper(candidates, target, 0, &[]int{}, &res)
    return res
}

func helper(nums []int, target, idx int, c *[]int, res *[][]int) {
    if target == 0 {
        tmp := make([]int, len(*c))
        copy(tmp, *c)
        *res = append(*res, tmp)
    } else if idx < len(nums) && target > 0 {
        // 跳过相同数字
        helper(nums, target, getNext(nums, idx), c, res)

        // 添加数字
        *c = append(*c, nums[idx])
        helper(nums, target-nums[idx], idx+1, c, res)
        
        // 回溯
        *c = (*c)[:len(*c)-1]
    }
}

func getNext(nums []int, idx int) int {
    i := idx
    for i < len(nums) && nums[i] == nums[idx] {
        i++
    }
    return i
}

13.2.5 问题83: 没有重复元素集合的全排列

LCR 083. 全排列

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

13.2.5.1 分析&题解

当选择位置i的数字时, [0, i-1]的数字都已经选过了, 那么就需要从[i, n-1]的数字中选.

func permute(nums []int) [][]int {
    res := [][]int{}
    helper(nums, 0, &res)
    return res
}

func helper(nums []int, idx int, res *[][]int) {
    // 所有数字已选定
    if idx == len(nums) - 1{
        tmp := make([]int, len(nums))
        copy(tmp, nums)
        *res = append(*res, tmp)
    } else {
        // 第i个位置的数字需要从 [i, n-1] 中选
        for j := idx; j < len(nums); j++ {
            swap(nums, idx, j)
            // 选定下一个
            helper(nums, idx+1, res)
            // 回溯
            swap(nums, idx, j)
        }
    }
}

func swap(nums []int, i, j int) {
    if i != j {
        nums[i], nums[j] = nums[j], nums[i]
    }
}

13.2.6 问题84: 包含重复元素集合的全排列

LCR 084. 全排列 II

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

13.2.6.1 分析&题解

由于包含重复数字, 交换的时候就需要跳过重复的数字.

可以使用HashSet存储已经交换过的数字, 如果没有交换才进行交换, 这样就能跳过重复数字.

func permuteUnique(nums []int) [][]int {
    res := [][]int{}
    helper(nums, 0, &res)
    return res
}

func helper(nums []int, idx int, res *[][]int) {
    if idx == len(nums) {
        tmp := make([]int, len(nums))
        copy(tmp, nums)
        *res = append(*res, tmp)
    } else {
        m := make(map[int]bool)
        for j := idx; j < len(nums); j++ {
            if !m[nums[j]] {
                m[nums[j]] = true
                swap(nums, j, idx)
                helper(nums, idx+1, res)
                swap(nums, j, idx)
            }
        }
    }
}

func swap(nums []int, i, j int) {
    if i != j {
        nums[i], nums[j] = nums[j], nums[i]
    }
}

Reference

1. 剑指Offer（专项突破版）