LeetCode 【40.组合总和 II】

冷不防 2022-04-13 14:53 225阅读 0赞

## LeetCode 【40.组合总和 II】 ##

**题目描述 ：**

给定一个数组`candidates`和一个目标数`target`,找出`candidates`中所有可以使数字和为`target` 的组合。

`candidates`中的每个数字在每个组合中只能使用一次。

**示例 1**

*  输入：candidates = \[10,1,2,7,6,1,5\],target = 8,
 *  所有解集为：

> \[
> 
> \[1,7\],
> 
> \[1,2,5\],
> 
> \[2,6\],
> 
> \[1,1,6\]
> 
> \]

**示例 2**

*  输入：candidates = \[2,5,2,1,2\],target = 5;
 *  所有解集为：

> \[
> 
> \[1,2,2\],
> 
> \[5\]
> 
> \]

**思路**

首先，需要对其数组进行排序，为什么呢？这样有利于去除重复的组合，在传参中需要继续向后进行递归，因为这里不需要多次使用原来的元素了。

**代码**

**完整代码**

package leetcode40;
    
    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>> combineSum(int[] candidates, int target) { 
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(candidates);
          // System.out.println(Arrays.toString(candidates));
            dfs(candidates, target, 0, new ArrayList<>(), res);
           // System.out.println(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));
            }
            for(int i = index; i < candidates.length; i ++) { 
                list.add(candidates[i]);
                dfs(candidates, target - candidates[i], i + 1, list, res);
                list.remove(list.size() - 1);
                while(i < candidates.length - 1 && candidates[i] == candidates[i+1]) i++;
            }
        }
    
    }
    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 IntegerlistToString(List<Integer> nums, int length) { 
            if(length == 0) { 
                return "[]";
            }
            String result = "";
            for(int num : nums) { 
                result += num;
                result += ", ";
            }
            return "[" + result.substring(0, result.length() - 2) +"]";
        }
        public static String int2dListToString(List<List<Integer>> nums) { 
    
            StringBuilder sb = new StringBuilder("[");
            for(List<Integer>list : nums) { 
                sb.append(IntegerlistToString(list));
                sb.append(",");
            }
            sb.setCharAt(sb.length() - 1, ']');
            return sb.toString();
        }
        public static String IntegerlistToString(List<Integer> nums) { 
            return  IntegerlistToString(nums, nums.size());
        }
        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[] candidates = stringToArrays(line);
               // System.out.println(Arrays.toString(candidates));
                int target = Integer.parseInt(in.readLine());
                //System.out.println(target);
                List<List<Integer>> ret = new Solution().combineSum(candidates, target);
               // System.out.println(ret.toString());
                String out = int2dListToString(ret);
                System.out.println(out);
            }
        }
    }