LeetCode【39.组合总数】

「爱情、让人受尽委屈。」 2022-04-13 14:47 162阅读 0赞

## leetcode【39.组合总数】 ##

**题目描述 ：**

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

**示例 1:**

*  输入： candidates = \[2,3,6,7\],target = 7;
 *  所求解集为：

> \[
> 
> \[7\],
> 
> \[2,2,3\]
> 
> \]

**示例 2:**

*  输入： candidates = \[2,3,5\],target = 8;
 *  所求解集为：

> \[
> 
> \[2,2,2,2\],
> 
> \[2,3,3\],
> 
> \[3,5\]
> 
> \]

**思路**

本题的要点在于可以无限制的使用重复的数字，所以在递归的时候需要再次使用**i**进行回溯，每次回溯需要将上次加入的元素删除，在递归中每次使用的循环需要从当前的索引开始；target小于0则直接返回；target等于0则直接加入res，（**注意：**`res.add(new ArrayList<>(list))`这个不需重新申请空间，再次赋值给res）。

**代码**

class Solution { 
        public List<List<Integer>> combinationSum(int[] candidates, int target) { 
            List<List<Integer>> res = new ArrayList<>();
            dfs(candidates, target, new ArrayList<>(), 0, res);
            return res;
        }
        public void dfs(int[] candidates, int target, List<Integer> list, int index, List<List<Integer>> res ) { 
            if(target < 0) { 
                return ;
            }
            if(target == 0) { 
                res.add(new ArrayList<>(list));
                return;
            }else{ 
                for(int i = index; i < candidates.length; i ++) { 
                    list.add(candidates[i]);
                    dfs(candidates, target - candidates[i], list, i, res);
                    list.remove(list.size() - 1);
                }
            }
        }
    }

**完整代码**

package leetcode39;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.StreamTokenizer;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /** * Created by 张超帅 on 2018/11/25. */
    class Solution { 
        public List<List<Integer>> combinationSum(int[] candidates, int target) { 
            List<List<Integer>> res = new ArrayList<>();
            dfs(candidates, target, 0, new ArrayList<>(), res);
            return res;
        }
        public void dfs(int[] candidates, int target, int index, List<Integer> list, List<List<Integer>> res){ 
            if(target < 0) { 
                return;
            }
            if(target == 0) { 
                res.add(new ArrayList<>(list));
                return;
            }
            for(int i = index; i < candidates.length; i ++) { 
                list.add(candidates[i]);
                dfs(candidates, target - candidates[i], i, list, res);
                list.remove(list.size() - 1);
            }
            return ;
        }
    }
    public class Main { 
        public static int[] StringToArrays(String input) { 
            input = input.trim();
            input = input.substring(1, input.length() - 1);
            if(input == null) { 
                return new int[0];
            }
            String[] parts = input.split(",");
            int[] res = new int[parts.length];
            for(int i = 0; i < parts.length; i++) { 
                res[i] = Integer.parseInt(parts[i].trim());
            }
            return res;
        }
        public static String integerArrayListToString(List<Integer> nums, int length) { 
            if(length == 0) { 
                return "[]";
            }
            String result = "";
            for(int i : nums) { 
                result += i;
                result += ", ";
            }
            return "[" + result.substring(0, result.length() - 2 ) +"]";
        }
        public static String integerArrayListToString(List<Integer> nums) { 
            return integerArrayListToString(nums, nums.size());
        }
        public static String int2dListToString(List<List<Integer>> nums) { 
            StringBuilder sb = new StringBuilder("[");
            for(List<Integer> list : nums) { 
                sb.append(integerArrayListToString(list));
                sb.append(",");
            }
            sb.setCharAt(sb.length() - 1, ']');
            return sb.toString();
        }
        public static void main(String[] args) throws IOException { 
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
           String line = null;
           while((line = in.readLine()) != null) { 
               int target = Integer.parseInt(in.readLine());
               int[] candidates = StringToArrays(line);
               List<List<Integer>> ret = new Solution().combinationSum(candidates, target);
               String out = int2dListToString(ret);
               System.out.println(out);
               //System.out.println(ret.toString());
           }
        }
    }