题解 | #加起来和为目标值的组合(三)#

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

https://www.nowcoder.com/practice/8c297161a58740c5b92b3e184dd1756e

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param n int整型 
     * @return int整型二维数组
     */
    ArrayList<ArrayList<Integer>> results = new ArrayList<>();
    int[] candicates = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
    public int[][] combination (int k, int n) {
        // write code here
        dfs(n,k,0,new ArrayList<Integer>());
        int[][] res = new int[results.size()][];
        for(int i = 0; i < res.length; i++){
            res[i] = new int[results.get(i).size()];
            for(int j = 0; j < results.get(i).size(); j++){
                res[i][j] = results.get(i).get(j);
            }
        }
        return res;
    }

    private void dfs(int rest,int k,int idx,ArrayList<Integer> path){
        if(rest < 0){
            return;     // 凑过头了,本次组合无效
        }
        if(path.size() == k){
            // 够k个数且凑足目标值了就添加答案
            if(rest == 0){
                results.add(new ArrayList<>(path));
            }
        }else{
            for(int i = idx; i < candicates.length; i++){
                path.add(candicates[i]);
                dfs(rest - candicates[i], k, i + 1, path);
                path.remove(path.size() - 1);
            }
        }
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 12:22
点赞 评论 收藏
分享
07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
码农索隆:想看offer细节
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 17:37
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务