Backtracking

Question 1

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Answer 1

Use backtracking and try to place every number in the current index, and recurse. Current permutation is fully done when we fill in all indices in the list

private void permute(int[] nums, int index, List<Integer> permutation, Set<Integer> visited, List<List<Integer>> result) {
    if (index==nums.length) {
        result.add(new ArrayList<>(permutation));
    } else {
        for(int i=0; i<nums.length; i++) {
            if (!visited.contains(nums[i])) {
                visited.add(nums[i]);
                permutation.add(nums[i]);
                permute(nums, index+1, permutation, visited, result);
                permutation.remove(permutation.size()-1);
                visited.remove(nums[i]);
            }
        }
    }
}

Call it:

    List<List<Integer>> result = new ArrayList<>();
    permute(nums, 0, new ArrayList<>(), new HashSet<>(), result);
    return result;

Question 2

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

Answer 2

Track number of open and closed paranthesis so far. If open is 0 or equal to closed then add (, else add either ( (if open < n) or ).
Backtrack to get all such strings

private void generate(int n, int open, int closed, StringBuilder sb, List<String> result) {
    if (sb.length()==2*n) {
        result.add(sb.toString());
        return;
    }
    List<Character> toAppend = new ArrayList<>();
    if (open==0) {
        toAppend.add('(');
    } else if (sb.length()==2*n-1) {
        toAppend.add(')');
    } else {
        if (open < n) {
            toAppend.add('(');
        } 
        if (closed < open) {
            toAppend.add(')');
        }
    }
    for(char c: toAppend) {
        sb.append(c);
        generate(n, c=='(' ? open+1:open, c==')'?closed+1 : closed, sb, result);
        sb.deleteCharAt(sb.length()-1);
    }
}

Call it:
int open = 0, closed = 0;
List<String> result = new ArrayList<>();
generate(n, open, closed, new StringBuilder(), result);
return result;</String>