# Combination Sum II: Java backtracking without sort

• ``````public class Solution { // 据说用中文注释会提高关注度
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// isVisited记录访问过的元素，防止重复访问 use isVisited to mark the elements which has been visited
Boolean[] isVisited = new Boolean[candidates.length];
Arrays.fill(isVisited, false);
dfs(candidates, new LinkedList<Integer>(), target, 0, 0, isVisited);
return lol;
}
// max 保证了产生的list是按升序排列 max ensures the generated list is nondecreasing
void dfs(int[] candidates, List<Integer> list, int target, int sum, int max, Boolean[] isVisited) {
if(sum > target) {return;}
Set<Integer> set = new HashSet<Integer>(); // 避免数组内重复出现的数对结果的影响 avoid duplicate
for(int i = 0; i < candidates.length; i++) {
if(candidates[i] >= max && !isVisited[i] && !set.contains(candidates[i])) {
isVisited[i] = true;
dfs(candidates, list, target, sum+candidates[i], candidates[i], isVisited);
isVisited[i] = false;
list.remove(list.size()-1);
}
}
}
}
``````

See more solution here:

Github
Blog

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.