Backtracking

Question 1

46. Permutations
    Medium

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

Example 1:

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

Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:

Input: nums = [1]
Output: [[1]]

Answer 1

class Solution {
List<List<Integer>> output = new ArrayList<>();</Integer>

public List<List<Integer>> permute(int[] nums) {

    List<Integer> tmpList = new ArrayList<>();
    bk(nums, tmpList);
    return output;
}

public void bk(int[] nums, List<Integer> tmpList) {
    if (tmpList.size() == nums.length) {
        output.add(new ArrayList<>(tmpList));
        return;
    }
    for (int n : nums) {
        if (tmpList.contains(n)) {
            continue;
        }
        tmpList.add(n);
        bk(nums, tmpList);
        tmpList.remove(tmpList.size() - 1);

    }
} }

Question 2

22. Generate Parentheses
    Medium

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

Example 1:

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

Input: n = 1
Output: [”()”]

Answer 2

class Solution {
List<String> li = new ArrayList<>();</String>

public List<String> generateParenthesis(int n) {
    dfs(n, 0, 0, "");
    return li;

}

public void dfs(int n, int open, int close, String s) {
    if (s.length() == 2 * n) {
        li.add(s);
        return;
    }
    if (open < n) {
        dfs(n, open + 1, close, s + "(");
    }
    if (close < open) {
        dfs(n, open, close + 1, s + ")");
    }
} }

Question 3

78. Subsets
    Solved

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Input: nums = [0]
Output: [[],[0]]

Answer 3

class Solution {
List<List<Integer>> result = new ArrayList<>();</Integer>

public List<List<Integer>> subsets(int[] nums) {

    List<Integer> subset = new ArrayList<>();
    dfs(nums, 0, subset);

    return result;
}

public void dfs(int[] nums, int startIndex, List<Integer> subset) {
    result.add(new ArrayList<>(subset));

    for (int i = startIndex; i < nums.length; i++) {
        subset.add(nums[i]);
        dfs(nums, i + 1, subset);
        subset.remove(subset.size() - 1);
    }
} }