# A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning)

• This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
for(int i = start; i < nums.length; i++){
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}

Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/

public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}

Permutations : https://leetcode.com/problems/permutations/

public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary
backtrack(list, new ArrayList<>(), nums);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
} else{
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])) continue; // element already exists, skip
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}

Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/

public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
if(tempList.size() == nums.length){
} else{
for(int i = 0; i < nums.length; i++){
if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
used[i] = true;
backtrack(list, tempList, nums, used);
used[i] = false;
tempList.remove(tempList.size() - 1);
}
}
}

Combination Sum : https://leetcode.com/problems/combination-sum/

public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
tempList.remove(tempList.size() - 1);
}
}
}

Combination Sum II (can't reuse same element) : https://leetcode.com/problems/combination-sum-ii/

public List<List<Integer>> combinationSum2(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;

}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
backtrack(list, tempList, nums, remain - nums[i], i + 1);
tempList.remove(tempList.size() - 1);
}
}
}

Palindrome Partitioning : https://leetcode.com/problems/palindrome-partitioning/

public List<List<String>> partition(String s) {
List<List<String>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), s, 0);
return list;
}

public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
if(start == s.length())
else{
for(int i = start; i < s.length(); i++){
if(isPalindrome(s, start, i)){
backtrack(list, tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
}

public boolean isPalindrome(String s, int low, int high){
while(low < high)
if(s.charAt(low++) != s.charAt(high--)) return false;
return true;
}

• I don't think sorting the nums array is useful in your Combination Sum solution. Your for loop condition should also contain '&& nums[i] <= remain'

• great summarization!

• @hide why the loop condition has to contian the '&&num[i] <= remain' ? wasn't this condition considered at first?

• @HaitaoSun Say remain is 7, and you have numbers 8,9,10,11,12,13,14,15,16....... up to a huge number.

If you put the condition in the for loop, it'll break out as soon as you see '8'. In OP's case, it'll check through all the numbers even when it could have just stopped after 8.

So actually, sorting the numbers CAN be useful, if you add the condition I stated to the for loop. Otherwise, sorting the numbers is useless because you aren't using the fact that they're sorted to prune your possible results.

• @hide you are so right! Thanks man!

• To generate anagrams of a Given String using same structure

List<String> anagrams (String input){
char[] inp = input.toCharArray();
List<String> result = new ArrayList();
backtrack(inp,result,inp.length,"");
return result;
}
void backtrack(char[] input,List result,final int size,String str) {
if(str.length()==size){  // or can be input.length
}
else{
for(int i =0 ;i<input.length;i++){
if(str.contains(""+input[i])){
continue;
}
String newStr = str + input[i];
backtrack(input,result,size,newStr);
}
}
}

• Nice post!
But in permutation,

if(tempList.contains(nums[i])) continue;

is O(n) complexity, right?
This makes the total complexity n^n instead of n! ?

• Hello . Fantastic summary ! I am trying to understand the reason behind !used[i - 1] for permutations II solution. Can you pls explain? Thank you.

• Hi, in the first one,list.add(new ArrayList<>(tempList));
If I use list.add(templist); directly, then it's emptly. But if I print the elements, they are in the templist. Why this happens? Thanks.

Got it. The templist will change later.

• @l78 I don't know either.Who can answer this question?

• @issac3 thanks so much for this!

• @smallskysky11 You need to create a COPY of templist before adding it. As you see templist keeps getting passed on as an argument and keeps getting modified. If you just add templist, all the modifications you make to templist get reflected in the final list.

• This post is deleted!

• @nksharath I also have the same doubt, Can anyone please explain? Thanks !!

• What is the time complexity of combination sum?

• @poojasunder27 I think it`s, O(k * 2 ^ n), where k is the average length of all the combinations and n is the size of nums

• @humachine Thanks you a lot!

• @nksharath you need '!used[i-1]' to differentiate whether we are processing the tempList which starts with 'i' or with 'i-1'.
If we started with 'i-1' then used[i-1] is still true in that case even though 'nums[i] == nums[i-1]' we should not skip it.
once we have finished processing 'i-1', used[i-1] is set to false and now processing 'i' doesn't make sense if nums[i]==nums[i-1] as it will generate the same results as 'i-1'

• @issac3
As for the problem Combination Sum, there is a typo in the Line 4: "new ArrayList<>( )" => "new ArrayList<Integer>( )".

After correcting this typo, this solution still cannot pass the test.

As for the test case [2, 2, 3], the output is [ [2, 2, 3], [2, 2, 3], [2, 2, 3] ], whereas the expected output is [ [2, 2, 3] ].

The reason is that there is duplicate "2"s in the given test case, which needs to be dealt with in the "for"-loop.

This is my solution to this problem.

public class Solution {
/**
* @param candidates: A list of integers
* @param target:An integer
* @return: A list of lists of integers
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> comb = new ArrayList<Integer>();
Arrays.sort(candidates);
helper(res, comb, target, 0, candidates);
return res;
}

private void helper(List<List<Integer>> res, List<Integer> comb, int remSum, int pos, int[] candidates) {
if (remSum == 0) {
// MUST "new ArrayList<Integer>(comb)", otherwise res = [[]] (empty)
return;
}
// remSum = target - sum(comb) > 0
for (int i = pos; i < candidates.length; i++) {
// prune following search
if (remSum - candidates[i] < 0) {
continue;
}
// avoid duplicates
if (i != pos && candidates[i] == candidates[i - 1]) {
continue;
}