39, 组合总和

一、题目描述

给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为target的不同组合数少于150个。

示例 1
输入: candidates = [2, 3, 6, 7], target = 7
输出: [[2, 2, 3], [7]]
解释: 2和3可以形成一组候选，2 + 2 + 3 = 7。注意2可以使用多次。7也是一个候选，7 = 7。仅有这两种组合。

示例 2
输入: candidates = [2, 3, 5], target = 8
输出: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

示例 3
输入: candidates = [2], target = 1
输出: []

提示

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates的所有元素互不相同
• 1 <= target <= 40

相关主题

• 数组
• 回溯

二、题解

方法 1: 回溯

pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    //Self::backtracking_1(candidates, target)
    Self::backtracking_2(candidates, target)
}

fn backtracking_1(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    const BACKTRACK: fn(usize, &[i32], i32, &mut Vec<i32>, &mut Vec<Vec<i32>>) =
        |idx, candidates, target, combine, res| {
            if target < 0 {
                return;
            }

            if target == 0 {
                res.push(combine.clone());
                return;
            }

            for i in idx..candidates.len() {
                combine.push(candidates[i]);

                BACKTRACK(i, candidates, target - candidates[i], combine, res);

                combine.pop();
            }
        };
    let mut res = vec![];

    BACKTRACK(0, &candidates, target, &mut vec![], &mut res);

    res
}

fn backtracking_2(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    const BACKTRACK: fn(usize, &[i32], i32, &mut Vec<i32>, &mut Vec<Vec<i32>>) =
        |idx, candidates, target, combine, res| {
            if idx == candidates.len() {
                return;
            }

            if target == 0 {
                res.push(combine.clone());
                return;
            }

            BACKTRACK(idx + 1, candidates, target, combine, res);

            if target - candidates[idx] >= 0 {
                combine.push(candidates[idx]);

                BACKTRACK(idx, candidates, target - candidates[idx], combine, res);

                combine.pop();
            }
        };
    let mut res = vec![];

    BACKTRACK(0, &candidates, target, &mut vec![], &mut res);

    res
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    //return this.backtracking1(candidates, target);
    return this.backtracking2(candidates, target);
}

@FunctionalInterface
interface QuintConsumer<A, B, C, D, E> {
    void accept(A a, B b, C c, D d, E e);
}

QuintConsumer<Integer, int[], Integer, List<Integer>, List<List<Integer>>> backtrack1 =
        (idx, candidates, target, combine, res) -> {
            if (target < 0) {
                return;
            }

            if (target == 0) {
                res.add(new ArrayList<>(combine));
                return;
            }

            for (int i = idx; i < candidates.length; i++) {
                combine.addLast(candidates[i]);

                this.backtrack1.accept(i, candidates, target - candidates[i], combine, res);

                combine.removeLast();
            }
        };

List<List<Integer>> backtracking1(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();

    this.backtrack1.accept(0, candidates, target, new ArrayList<>(), res);

    return res;
}

QuintConsumer<Integer, int[], Integer, List<Integer>, List<List<Integer>>> backtrack2 =
        (idx, candidates, target, combine, res) -> {
            if (idx == candidates.length) {
                return;
            }

            if (target == 0) {
                res.add(new ArrayList<>(combine));
                return;
            }

            this.backtrack2.accept(idx + 1, candidates, target, combine, res);

            if (target - candidates[idx] >= 0) {
                combine.addLast(candidates[idx]);

                this.backtrack2.accept(idx, candidates, target - candidates[idx], combine, res);
                
                combine.removeLast();
            }
        };

List<List<Integer>> backtracking2(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();

    this.backtrack2.accept(0, candidates, target, new ArrayList<>(), res);

    return res;
}