[LeetCode] 39. 组合总和（java实现）dfs_dfs算法之leetcode实战ja va

1. 题目

2. 读题（需要重点注意的东西）

思路（dfs）：
这种类似于凑组合数的题，可以使用类似排列数字的方法，即dfs
整体的思路与- [AcWing]842. 排列数字（C++实现）dfs模板题，递归思想的解释大致相当，在此不再赘述。

3. 解法

---------------------------------------------------解法---------------------------------------------------：

class Solution {
    public List<List<Integer>> list = new ArrayList<>();
    public List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,0,target);
        return list;
    }
    public void dfs(int[] candidates,int u,int target){
        if(target == 0){
            /*
            list.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到list
            list.add(path)：将list尾部指向了path地址，后续path内容的变化会导致list的变化。 
            */
            list.add(new ArrayList(path)); 
            return;
        }
        // 数已经选完了，不能组成target，直接返回
        if(u == candidates.length) return;

        // 选i个candidates[u]，条件是不能超过target
        for(int i = 0;candidates[u] * i <= target;i++){
            // 存入选了i个candidates[u]
            for(int j = 0;j < i;j++) path.add(candidates[u]);
            // 选下一个数u+1
            dfs(candidates,u+1,target - candidates[u] * i);
            // 恢复现场
            for(int k = 0;k < i;k++) path.remove((Integer)candidates[u]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

可能存在的问题：
问题一：为什么打印出来的结果为[[ ],[ ],…]？
答:
①list.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到list；
②list.add(path)：将list尾部指向了path地址，后续path内容的变化会导致list的变化。

问题二：此处(Integer)candidates[u]为什么要将int转为Integer？
答:
list.remove()有两种使用方式：
①当传入的值为int型时，删除指定下标的值，如remove(2)；
②当传入的值为Object型时，如Integer、String，会删除第一个找到的Object值,如remove(“hello”)。

4. 可能有帮助的前置习题

• [AcWing]842. 排列数字（C++实现）dfs模板题，递归思想的解释

5. 所用到的数据结构与算法思想

• Java数据结构—List（链表、顺序表的定义及其基本操作）
• dfs

6. 总结

① 掌握dfs在排列组合数字方面的应用；
② 注意list.add和list.remove的使用方法。