39. Combination Sum

https://leetcode.com/problems/combination-sum/

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations
of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times.
Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150
combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

给 元素不重复 无序 数组，求满足条件的子数组，组合问题
需要子数组满足的条件：子数组元素和等于某个数

package leetcode.problems.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtrack(result, candidates, path, 0, target);
        return result;
    }

    /**
     * 1. 画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
     * 2. 根据题意，确立结束条件
     * 3. 找准选择列表(与函数参数相关),与第一步紧密关联※
     * 4. 判断是否需要剪枝
     * 5. 作出选择，递归调用，进入下一层
     * 6. 撤销选择 返回上一层
     * @param result
     * @param candidates
     * @param start
     * @param stillNeed
     */
    private void backtrack(List<List<Integer>> result, int[] candidates, List<Integer> path, int start, int stillNeed) {
        if (stillNeed < 0) {
            return;
        } else if (stillNeed == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            backtrack(result, candidates, path, i, stillNeed-candidates[i]);
            path.remove(path.size()-1);
        }
    }
}