Backtracking.java

// 1. word break 1
public boolean dfs(String s, List<String> wordDict) {
	return dfs(s, new HashSet<>(wordDict), 0);
}

public boolean dfs(String s, Set<String> wordDict, int start) {
	if (start == s.length()) {
		return true;
	}
	for (int end =	 start + 1; end <= s.length(); end++) {
		if (wordDict.contains(s.substring(start, end)) && dfs(s, wordDict, end)) {
			return true;
		}
	}
	return false;
}

// word break 2

public List<String> wordBreak(String s, Set<String> wordDict) {
    return word_Break(s, wordDict, 0);
}
public List<String> word_Break(String s, Set<String> wordDict, int start) {
    LinkedList<String> res = new LinkedList<>();
    if (start == s.length()) {
        res.add("");
    }
    for (int end = start + 1; end <= s.length(); end++) {
        if (wordDict.contains(s.substring(start, end))) {
            List<String> list = word_Break(s, wordDict, end);
            for (String l : list) {
                res.add(s.substring(start, end) + (l.equals("") ? "" : " ") + l);
            }
        }
    }
    return res;
}

// 2. subset sum 1
public List<List<Integer>> subsets(int[] nums) {
	List<List<Integer>> result = new ArrayList<>(); List<Integer> cur = new ArrayList<>();
	backtrack(result, cur, nums, 0);
	return result;
}

public void backtrack(List<List<Integer>> result, List<Integer> cur, int[] nums, int start){
	result.add(new ArrayList<>(cur));
	for (int i = start; i < nums.length; i++){
		cur.add(nums[i]);
		backtrack(result, cur, nums, i+1);
		cur.remove(cur.size()-1);
	}
}

// subset sum 2
public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> result = new ArrayList<>(); List<Integer> cur = new ArrayList<>();
    Arrays.sort(nums); // sort inputs
    backtrack(result, cur, nums, 0);
    return result;
}

public void backtrack(List<List<Integer>> result, List<Integer> cur, int[] nums, int start){
    result.add(new ArrayList<>(cur));
    for (int i = start; i < nums.length; i++){
        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
        cur.add(nums[i]);
        backtrack(result, cur, nums, i+1);
        cur.remove(cur.size()-1);
    }
}


// 3. combination sum 1

public List<List<Integer>> combinationSum(int[] candidates, int target) {
	if (candidates == null || candidates.length == 0) return new ArrayList<List<Integer>>();
	// Arrays.sort(candidates); // no sort needed as array elements gonna be sorted
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> cur = new ArrayList<>();
	backtrack(result, cur, candidates, 0, target);
	return result;   
}

public void backtrack(List<List<Integer>> result, List<Integer> cur, int[] nums, int start, int target){
	if (target == 0){
		List<Integer> temp = new ArrayList<>(cur);
		result.add(temp);
		return;
	}
	else if (target > 0){
		for (int i = start; i < nums.length; i++){
			cur.add(nums[i]);
			backtrack(result, cur, nums, i, target-nums[i]);
			cur.remove(cur.size()-1);
		}
	}
}

// combination sum 2
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
	if (candidates == null || candidates.length == 0) return new ArrayList<List<Integer>>();
	Arrays.sort(candidates); // why are we sorting?
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> cur = new ArrayList<>();
	backtrack(result, cur, candidates, 0, target);
	return result;  
}

public void backtrack(List<List<Integer>> result, List<Integer> cur, int[] nums, int start, int target){
	if (target == 0 && cur.size() > 0){
		result.add(new ArrayList<>(cur)); // to avoid shallow copy
		System.out.println("\n");
		cur.forEach(x -> System.out.print(x + " "));
		return;
	}
	else if (target > 0){
		for (int i = start; i < nums.length; i++){
			if ( i > start && nums[i] == nums[i-1]) continue; // new- skip duplicates 
			cur.add(nums[i]);
			backtrack(result, cur, nums, i + 1, target-nums[i]); // new- dont pick same index hence i+1
			cur.remove(cur.size()-1);
		}
	}
}