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

• 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;
}
``````

• 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);
}
}
}
``````

tempList.remove(tempList.size() - 1);

• Elegant and concise. Thank you.

• @Juan55555 To generate all possible permutations, we need to remove the least recently added element while we are going up the recursive call stack.
In the first iteration of the `for` loop we add all permutations, that start with `nums[0]`. Then, before we can begin building all permutations starting with `nums[1]`, we need to clear the `tempList` (which currently contains permutations from the first iteration of the `for` loop) - that's exactly what `tempList.remove(tempList.size() - 1)` line does.

• This answer is highly underrated..

• awesome summary! love it!

• @issac3 This is great answer! Thanks a lot for combining all the approaches. I have doubt the purpose of below line in Permutation II problem. Can you confirm about its purpose please ? Thanks.

``        if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;``

• ``````if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;

``````

in the above line, could you explain nums[i] == nums[i-1] && !used[i - 1] this ?

Thanks.

• This post is deleted!

we use [1a,1b,1c,1d] to mark the four 1s. with the

if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;

we make sure that 1a element is added to the result first, then 1b, then 1c, then 1d. In this case, we can only get 1 result. instead of getting 4!.

• @dreamer92 Hello, here is the meaning of the line you pointed out:
You should notice that the array "nums" is sorted before we call the "backtrack" function, so this line simply means "if an element is already used in the permutation, we skip it OR if an element equals to the element before it, and the element before this element is not used in the permutation yet, we also skip it". In this way, we ensure the result is correct. Hope this answers your question :)

• The code in Permutation II:
I was wondering if you made a mistake
the condition should be i > 0 && nums[i] == nums[i - 1] && used[i - 1]
not !used[i-1].
because only if i-1 was used and i equals i-1,we can skip this.

• @toddler the purpose of checking if used[i-1] is to make sure the order of same value does not change, so of [1,1,2]. the second 1 cannot be used if the first has not been used yet, which means when(!used[i-1]) we skip the second 1.

• This approach can also be applied to the combinations problem
https://leetcode.com/problems/combinations/

``````public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list=new ArrayList<List<Integer>>();
backtrack(list,new ArrayList<Integer>(),n,k,1);
return list;
}
public void backtrack(List<List<Integer>> list,ArrayList<Integer> templist,int n, int k,int start){
if(templist.size()==k)
else if(templist.size()>k)return;

for(int i=start;i<=n;i++){
backtrack(list,templist,n,k,i+1);
templist.remove(templist.size()-1);
}
}
``````

• @bumblebeem @wondershow @Oliiiviiiaaa @issac3 I still am unsure of what the following line means? Could you please elaborate a little on it?

``````if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
``````

Also for subsets i, why are we `sorting` the arrays?

What are the `complexities` of these algorithms? If we use sort, it is `O(nlogn)` otherwise `O(n)`, is it?

• @vivekpatani I don't think there will be any O(n) or even O(nlogn) algorithm with this problem

• Isn't the following line has O(n) complexity?
if(tempList.contains(nums[i])) continue;

• @csytracy Yes it is. The alternative would be to keep a boolean array to see which entries have already been used.

``````private void permute(int[] nums, boolean[] seen, List<List<Integer>> result, Stack<Integer> current) {
if (current.size() == nums.length) {
}

for (int i = 0; i < nums.length; i++) {
if (!seen[i]) {
current.push(nums[i]);
seen[i] = true;
permute(nums, seen, result, current);
seen[i] = false;
current.pop();
}
}
}
``````

The problem with this is that we need O(n) extra space. This does not matter asymptotically since we already allocate that much space to track the current numbers. We could combine current and seen by using a map. But this would make the code a bit more ugly.

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