Lintcode 135 · 数字组合【中的 排列组合问题 DFS Java】

题目

题目链接： https://www.lintcode.com/problem/135

思路

经典的组合问题：
需要注意的是：需要去重，因为题目要求unique combinations
需要提前排序，因为题目要求结果输出ascending order
注意递归的出口
每个数字可以重复用，所以startIndex传入下一层递归时不加1

Java代码

public class Solution {/*** @param candidates: A list of integers* @param target: An integer* @return: A list of lists of integers*          we will sort your return value in output*/public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<>();Set<String>  visited = new HashSet<>();List<Integer> path = new ArrayList<>();Arrays.sort(candidates);dfs(candidates,0,0,target,path,visited,ans);return ans;}public void dfs(int[] arr,int idx,int sum,int target,List<Integer> path,Set<String> visited,List<List<Integer>> ans){if(sum> target) return;if(sum == target){if(visited.contains(path.toString()))return;ans.add(new ArrayList<>(path));visited.add(path.toString());}else{for (int i = idx; i <arr.length; i++) {path.add(arr[i]);dfs(arr,i,sum+arr[i],target,path,visited,ans);path.remove(path.size()-1);  //恢复现场}}}}