My 16ms Java backtracking solution beats 97.64%


  • 0
    A

    public class Solution {

    static boolean[] visited = null;
    public List<List<Integer>> combinationSum2(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList();
        if(nums.length == 0 || target == 0) {
            return list;            
        }
        Arrays.sort(nums);
        
        visited = new boolean[nums.length];
        List<Integer> list2 = new ArrayList();
        combinationSum(nums,0,target,list,list2);
        return list;
    }
    
    public static void combinationSum(int[] nums, int start, int target, List<List<Integer>> list, List<Integer> list2) {
        
    
        if(target == 0) {
            list.add(new ArrayList(list2));
            return;
        }
        
        if( start >= nums.length || nums[start] > target) {
            return;
        }
        
        for(int i = start; i < nums.length ; i++) {
            if(nums[i] > target) {
                break;
            }
            if(i >= 1 && nums[i] == nums[i-1] && visited[i-1] == false) {
                continue;
            }
            list2.add(nums[i]);
            visited[i] = true;
            combinationSum(nums,i+1,target-nums[i],list,list2);
            list2.remove(list2.size()-1);
            visited[i] = false;
        }
    }
    

    }


Log in to reply
 

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