Combination Sum II: Java backtracking without sort


  • 1
    C
    public class Solution { // 据说用中文注释会提高关注度
        List<List<Integer>> lol = new LinkedList<List<Integer>>();
        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;}
            if(sum == target) {lol.add(new LinkedList<Integer>(list));}
            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])) {
                    set.add(candidates[i]);
                    isVisited[i] = true;
                    list.add(candidates[i]);
                    dfs(candidates, list, target, sum+candidates[i], candidates[i], isVisited); 
                    isVisited[i] = false;
                    list.remove(list.size()-1);
                }
            }
        }
    }
    

    See more solution here:

    Github
    Blog

Log in to reply
 

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