当前位置：首页 > article >正文

LeetCode 216-组合总数Ⅲ

article 2024/12/27 23:28:34

题目链接：LeetCode216

欢迎留言交流，每天都会回消息。

class Solution {
    List<List<Integer>> rs = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 0, 1);
        return rs;
    }
	
	//num：数字的个数
	//target：num 个数字的总和
    void backTracking(int num, int target, int sum, int startIdx){
		//数字的个数为 num 时终止，如果和等于 target 将数组添加到最终的结果 rs 中
        if(path.size() == num){
            if(sum == target)
                rs.add(new ArrayList<>(path));
            return;
        }
		//不重复的遍历1-9，startIdx从1开始
        for(int i = startIdx; i <= 9; i++){
            sum += i;
            path.add(i);
            //递归调用
            backTracking(num, target, sum, i + 1);
            //回溯
            path.removeLast();
            sum -= i;
        }
    }
}