【LeetCode】【HOT】39. 组合总和（回溯）

【LeetCode】【HOT】39. 组合总和

package hot;

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

public class Solution39 {
    public static void main(String[] args) {
        int[] nums = {2,3,6,7};
        Solution39 solution = new Solution39();
        System.out.println(solution.method(nums, 7));
    }

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

    public List> method(int[] candidates, int target){
        dfs(candidates, 0, target);
        return res;
    }

    public void dfs(int[] c, int u, int target){
        if(target < 0) return;
        if(target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = u; i < c.length; i++){
            if(c[i] <= target){
                path.add(c[i]);
                dfs(c, i, target - c[i]);
                path.remove(path.size() - 1);   //回溯
            }
        }
    }
}

//最差时间复杂度为 O(n*2^n)
//空间复杂度为 O(n)