这是一个简单的排列组合问题,输入n和k的值返回在n中取k个元素的所有组合。
采用go实现如下:
func combine(n int, k int) [][]int {
var ans [][]int = [][]int{}
var findKElms func([]int,int,int)
findKElms = func (tempElms []int, n,k int){
if len(tempElms) == k{
ans = append(ans, tempElms)
return
}else{
if n - tempElms[len(tempElms)-1] + len(tempElms) >= k{
for i := tempElms[len(tempElms)-1] + 1; i <= n - (k - len(tempElms)) + 1; i ++{
hh := append(tempElms,i)
findKElms(hh,n,k)
}
}
}
}
for i := 1; i <= n - k + 1; i ++{
hh := []int{i}
findKElms(hh,n,k)
}
return ans
}
在k <= 3时运行没有任何问题;
但在k >= 4时,运行总是出现一些问题:
例如n = 5,k = 4时:
对于这种情况,经过一些调试发现现象:能够找到每一个组合,例如第一个组合[1,2,3,4],将其加入答案数组时,在找到下一个排列[1,2,3,5]时,发现答案中原本包含的[[1,2,3,4]]居然变成了[[1,2,3,5]],不是很理解。先是以为某处发生了覆盖,但找不到地方,且对于 k <= 3的情况却也没有发生这种情况。
希望大家能够帮忙解决解决。
用递归法求解:
package main
import (
"fmt"
)
func sublist(s []int, length int, i int, t []int) {
if i == len(s) {
if len(t) == length {
fmt.Println(t)
}
return
}
sublist(s, length, i+1, append(t, s[i]))
sublist(s, length, i+1, t)
}
func main() {
sublist([]int{1, 2, 3, 4, 5}, 4, 0, []int{})
sublist([]int{1, 2, 3, 4, 5, 6}, 3, 0, []int{})
}
输出:
[1 2 3 4]
[1 2 3 5]
[1 2 4 5]
[1 3 4 5]
[2 3 4 5]
[1 2 3]
[1 2 4]
[1 2 5]
[1 2 6]
[1 3 4]
[1 3 5]
[1 3 6]
[1 4 5]
[1 4 6]
[1 5 6]
[2 3 4]
[2 3 5]
[2 3 6]
[2 4 5]
[2 4 6]
[2 5 6]
[3 4 5]
[3 4 6]
[3 5 6]
[4 5 6]
成功: 进程退出代码 0.