排列组合

author:魏静崎
2024年10月16日
算法

组合

组合就是从n个中选取k个的枚举。
使用递归回溯的办法进行，每一层选取一个元素，并创建新的分支，递归到k层即可停止。
1. 组合之间不能重复，因此需要剪枝，向下一层递归时，候选元素只选取大于当前值的节点，可以切片也可以加入current_val作为记录。
2. 但是这样会出现元素不足的情况，如还需要两个元素，但是只有一个大于当前元素的值，因此还需要判断元素的个数是否足够，如果可以使用1-n的所有元素则，候选数组范围为[cur_val, n-(k-depth)+1]

func combine(n int, k int) [][]int {  
    var res [][]int  
    helper(n, k, 1, []int{}, &res)  
    return res  
}  
  
func helper(n int, k int, curVal int, tmp []int, res *[][]int) {  
    if len(tmp) == k { // 组合长度等于k，则将tmp加入res  
       *res = append(*res, append([]int{}, tmp...))  // 这里要用append([]int{}, tmp...)，否则会导致tmp的地址变化，导致res中存放的都是同一个tmp
       return  
    }  
    for i := curVal; i <= n; i++ {  
       tmp = append(tmp, i)  
       helper(n, k, i+1, tmp, res)  
       tmp = tmp[:len(tmp)-1] // 回溯，删除最后一个刚加入的元素  
    }  
}

• **tmp...**：这是一个切片展开语法（spread syntax），用于将切片 tmp 的元素逐个添加到新切片中。这个语法的作用是将 tmp 中的所有元素传递给 append 函数。

排列

排列就是一次选取一个元素，将列表中的其他元素传给下一层即可。

func permute(nums []int) [][]int {  
    var res [][]int  
    permuteHelper(nums, []int{}, &res)  
    return res  
}  
  
func permuteHelper(nums []int, tmp []int, res *[][]int) {  
    if len(nums) == 0 {  
       *res = append(*res, append([]int{}, tmp...))  
       return  
    }  
    // 遍历nums中的每个元素，将剩余的元素作为参数传入  
    for i := 0; i < len(nums); i++ {  
       tmp = append(tmp, nums[i])  
       // 去除nums[i]  
       copySlice := make([]int, len(nums))  
       copy(copySlice, nums)  
       nums = append(nums[:i], nums[i+1:]...)  
  
       // 递归调用  
       permuteHelper(nums, tmp, res)  
       nums = copySlice  
       tmp = tmp[:len(tmp)-1] // 回溯，删除最后一个刚加入的元素  
    }  
}

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： 魏静崎
• 本文链接： https://slightwjq.github.io/2024/10/16/排列组合/
• 版权声明： 该文章来源及最终解释权归作者所有