加起来和为目标值的组合(三)

[编程题]加起来和为目标值的组合(三)

热度指数：1799 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

找出所有相加之和是 n 的 k 个数的组合。组合中只含有 1~9的正整数，且保证每种组合中不含有相同的数字。

保证一定有解。结果按字典序升序输出。

示例1

输入

3,7

输出

[[1,2,4]]

示例2

输入

2,3

输出

[[1,2]]

示例3

输入

2,5

输出

[[1,4],[2,3]]

算法知识视频讲解

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param k int整型 
 * @param n int整型 
 * @return int整型二维数组
*/
func combination( k int ,  n int ) [][]int {
    ans:=[][]int{}
    var back_tracking func([]int,int,int)
    back_tracking=func(path []int,sum int,idx int){
        if sum>=n{
            if len(path)==k&&sum==n{
                tmp:=make([]int,len(path))
                copy(tmp,path)
                ans=append(ans,tmp)
            }
            return
        }
        if len(path)>k{
            return
        }
        for i:=idx;i<n;i++{
            path=append(path,i)
            sum+=i
            back_tracking(path,sum,i+1)
            path=path[:len(path)-1]
            sum-=i
        }
    }
    back_tracking([]int{},0,1)
    return ans
}

发表于 2023-03-08 23:45:24 回复(0)