Backtracking solution using java


  • 0
    H
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    		List<List<Integer>> list = new ArrayList<>();
    		Arrays.sort(candidates);
    		ArrayList<Integer> tackingList = new ArrayList<>();
    		combinationSumUtil(candidates, 0, target, list, tackingList);
    		return list;
    	}
    
    	private void combinationSumUtil(int[] array, int index, int target, List<List<Integer>> list,
    			ArrayList<Integer> trackingList) {
    		if (target == 0) {
    			ArrayList<Integer> arrayList = new ArrayList<>();
    			for (Iterator<Integer> iterator = trackingList.iterator(); iterator.hasNext();) {
    				Integer integer = iterator.next();
    				arrayList.add(integer);
    			}
    			Collections.sort(arrayList);
    			for (List<Integer> smallerList : list) {
    				if (smallerList.equals(arrayList))
    					return;
    			}
    			list.add(arrayList);
    			return;
    		}
    		if (index >= array.length || target < array[index]) {
    			return;
    		}
    		trackingList.add(array[index]);
    		combinationSumUtil(array, index + 1, target - array[index], list, trackingList);
    		trackingList.remove(trackingList.size() - 1);
    		combinationSumUtil(array, index + 1, target, list, trackingList);
    	}
    

Log in to reply
 

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