[数据结构与算法]39. 组合总和

算法记录

LeetCode 题目：

??给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

说明

一、题目

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

二、分析

• 每个数据可以有两种选择, 一是不计入当前的求和列表, 二是计入当前的求和列表并统计数据.
• 也就可以抽象为一棵二叉树, 但是需要注意每次选取当前数之后下一次依然是可选取的, 每次的数据进行保存之后需要进行一次路径的返回, 不然会造成相同的列表的叠加.

class Solution {
    private List<List<Integer>> ans = new ArrayList();
    private List<Integer> temp = new ArrayList(); 
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(0, candidates, target);
        return ans;
    }
    private void dfs(int idx, int[] candidates, int target) {
        if(idx == candidates.length) return ;
        if(target < 0) return ;
        if(target == 0) {
            ans.add(new ArrayList(temp));
            return ;
        }
        temp.add(candidates[idx]);
        dfs(idx, candidates, target - candidates[idx]);
        temp.remove(temp.size() - 1);
        dfs(idx + 1, candidates ,target);
    }
}

总结

熟悉深度优先搜索的展开。