LeetCode 216. Combination Sum II

Problem

LeetCode 216. Combination Sum II

1. 题目简述

给出一个目标数n，在1到9中找k个数，使得k个数之和为n（每个数字至多选择一次）。例如：

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

2. 算法思路

回溯

这道题是combination sum系列的第三题，又是不重复的数字，且每个数字至多只能选一次，而且要求一定是k个。

限制条件变多，但依然是用回溯法做，每次判断下一层的时候记得k-1，且最终add结果时判断k是否为k-1是否为0。数字为1-9，这次不需要传数组进去了，直接用数字就好。

3. 解法

1. 回溯，记得如果更改了k的话也要将k复原，回溯法一定注意复原！

class Solution {

    List<List<Integer>> res = new ArrayList();

    public List<List<Integer>> combinationSum3(int k, int n) {
        LinkedList<Integer> nums = new LinkedList();

        backtracking(n, 0, 1, nums, k);

        return res;
    }

    private void backtracking(int target, int sum, int start, LinkedList<Integer> nums, int k) {
        for (int i = start; i < 10; i++) {
            sum += i;
            nums.add(i);

            if (sum < target) {
                backtracking(target, sum, i + 1, nums, k - 1);
                nums.removeLast();
                sum -= i;
                continue;
            } else if (sum == target && k - 1 == 0) {
                res.add(new ArrayList(nums));
            }

            nums.removeLast();
            return;
        }
    }
}