Summary: Problems solved with DFS recursions II (NP Problems)

interview

---

SORT the fucking given array/number set if the output requires ascending order

1. Permutations

Permutations I

Given a collection of numbers, return all possible permutations.

Key:
Mark visited numbers:
if visited, continue to next number;
otherwise, use current number in current permutation, then mark it visited

Example, [1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

public void dfs(List<List<Integer>> res, int[] nums, ArrayList<Integer> sol, boolean [] visited){
    if(sol.size() == nums.length){
        List<Integer> path = new ArrayList<Integer>(sol);
        res.add(path);
        return ;
    }
    for(int i=0; i<nums.length; i++){
        if(visited[i]) continue;
        visited[i]=true;
        sol.add(nums[i]);
        dfs(res, nums, sol, visited);
        sol.remove(sol.size()-1);
        visited[i]=false;
    }
}
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    int n = nums.length;
    if(n==0) return res;
    ArrayList<Integer> sol = new ArrayList<Integer>();
    boolean visited [] = new boolean [n];
    Arrays.sort(nums);
    dfs(res, nums, sol, visited);
    return res;
}

PermutationsII

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

public void dfs(List<List<Integer>> res, int[] nums, ArrayList<Integer> sol, boolean [] visited){
    if(sol.size() == nums.length){
        List<Integer> path = new ArrayList<Integer>(sol);
        res.add(path);
        return ;
    }
    for(int i=0; i<nums.length; i++){
        if(visited[i]) continue;
        if(i>0 && nums[i]==nums[i-1] && visited[i-1]) continue; // mistake : must check visited
        visited[i]=true;
        sol.add(nums[i]);
        dfs(res, nums, sol, visited);
        sol.remove(sol.size()-1);
        visited[i]=false;
    }
}
public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    int n = nums.length;
    if(n==0) return res;
    ArrayList<Integer> sol = new ArrayList<Integer>();
    boolean visited [] = new boolean [n];
    Arrays.sort(nums);
    dfs(res, nums, sol, visited);
    return res;
}

2. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

public void dfs(List<List<Integer>> res, ArrayList<Integer> sol, int n, int k, int cur){
    if(sol.size()==k) {
        List<Integer> path = new ArrayList<Integer>(sol);
        res.add(path);
        return;
    }
    for(int i=cur; i<=n; i++){
        sol.add(i);
        dfs(res, sol, n, k, i+1);
        sol.remove(sol.size()-1);
    }
}
public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(n==0) return res;
    ArrayList<Integer> sol = new ArrayList<Integer>();
    dfs(res, sol, n, k, 1);
    return res;
}

3. Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

• All numbers (including target) will be positive integers.
• Elements in a combination $(a_1, a_2, \ldots , a_k)$ must be in non-descending order. $(ie, a_1 \leq a_2 \leq \ldots \leq a_k)$.
• The solution set must not contain duplicate combinations.

Combination Sum I

The same repeated number may be chosen from C unlimited number of times.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

public class Solution {
    public void dfs(List<List<Integer>> res, int[] candidates, ArrayList<Integer> sol, int cur_idx, int cur_sum, int target){
        if(cur_sum==target){
            List<Integer> path = new ArrayList<Integer>(sol);
            res.add(path);
            return;
        }
        if(cur_idx == candidates.length) return;
        if(cur_sum>target) return;
        for(int i=cur_idx; i<candidates.length; i++){
            sol.add(candidates[i]);
            dfs(res, candidates, sol, i, cur_sum+candidates[i], target); // use the same number
            sol.remove(sol.size()-1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int n = candidates.length;
        if(n==0) return res;
        ArrayList<Integer> sol = new ArrayList<Integer>();
        Arrays.sort(candidates);
        dfs(res, candidates, sol, 0, 0, target);
        return res;
    }
}

Combination Sum II

Each number in C may only be used once in the combination.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

public class Solution {
    public void dfs(List<List<Integer>> res, int[] candidates, ArrayList<Integer> sol, int cur_idx, int cur_sum, int target){
        if(cur_sum==target){
            List<Integer> path = new ArrayList<Integer>(sol);
            res.add(path);
            return;
        }
        if(cur_idx == candidates.length) return;
        if(cur_sum>target) return;
        for(int i=cur_idx; i<candidates.length; i++){
            if(i>cur_idx && candidates[i]==candidates[i-1]) continue; // pass duplicates
            sol.add(candidates[i]);
            dfs(res, candidates, sol, i+1, cur_sum+candidates[i], target); // pass next 
            sol.remove(sol.size()-1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int n = candidates.length;
        if(n==0) return res;
        ArrayList<Integer> sol = new ArrayList<Integer>();
        Arrays.sort(candidates);
        dfs(res, candidates, sol, 0, 0, target);
        return res;
    }
}

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

• Ensure that numbers within the set are sorted in ascending order.

Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2:
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

Idea:
Similar to combination I and II, just modify different termination condition.

public void dfs(List<List<Integer>> res, ArrayList<Integer> sol, int k, int target, int cur, int cur_sum){
    if(cur_sum > target || sol.size()>k ) return;
    if(cur_sum == target && sol.size() == k){
        List<Integer> path = new ArrayList<Integer>(sol);
        res.add(path);
        return;
    }
    for(int i=cur; i<=9; i++){
        sol.add(i);
        dfs(res, sol, k, target, i+1, cur_sum+i);
        sol.remove(sol.size()-1);
    }
}
public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(k==0|| n<=0) return res;
    ArrayList<Integer> sol = new ArrayList<Integer>();
    dfs(res, sol, k, n, 1, 0);
    return res;
}

5. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Example: Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return
[
[5,4,11,2],
[5,8,4,5]
]

Idea:
sum values of nodes from root to leaf, add to results if sum $\neq$ target number

public void dfs(List<List<Integer>> res, ArrayList<Integer> sol, TreeNode root, int cur_sum, int target){
    //if(cur_sum>target) return;
    // mistake when negative node vals
    if(root==null) return;
        sol.add(root.val);
        cur_sum += root.val;
        if(cur_sum==target && root.left==null && root.right==null){ 
            // leaf node check
            List<Integer> path = new ArrayList<Integer>(sol);
            res.add(path);
            return;
        }
    }
    // can not pass sol directly, in java, sol is an object
    ArrayList<Integer> sol1 = new ArrayList<Integer>(sol);
    dfs(res, sol1, root.left, cur_sum, target);
    ArrayList<Integer> sol2 = new ArrayList<Integer>(sol);
    dfs(res, sol2, root.right, cur_sum, target);
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(root == null) return res;
    ArrayList<Integer> sol = new ArrayList<Integer>();
    dfs(res, sol, root, 0, sum);
    return res;
}

6. Subsets

Subsets I

Given a set of distinct integers, nums, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

Idea:
For each number $i$ in the given set, we can form a subset with or without it.

public void dfs(List<List<Integer>> res, ArrayList<Integer> sol, int[] nums, int cur_idx){
    if(cur_idx == nums.length){
        List<Integer> path = new ArrayList<Integer>(sol);
        res.add(path);
        return;
    }
    // pass by current element
    dfs(res, sol, nums, cur_idx+1);
    // add current element to subset
    sol.add(nums[cur_idx]);
    dfs(res, sol, nums, cur_idx+1);
    sol.remove(sol.size()-1);
}
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(nums.length==0) return res;
    ArrayList<Integer> sol = new ArrayList<Integer>();
    Arrays.sort(nums);
    dfs(res, sol, nums, 0);
    return res;
}

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

public void dfs(List<List<Integer>> res, ArrayList<Integer> sol, int[] nums, int cur_idx){
    if(!res.contains(sol)){
        List<Integer> path = new ArrayList<Integer>(sol);
        res.add(path);
        // return; // mistake : do not return
    }
    for(int i=cur_idx; i<nums.length; i++){
        sol.add(nums[i]);
        dfs(res, sol, nums, i+1);
        sol.remove(sol.size()-1);
    }
}
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(nums.length==0) return res;
    ArrayList<Integer> sol = new ArrayList<Integer>();
    Arrays.sort(nums);
    dfs(res, sol, nums, 0);
    return res;
}

7. N Queens

N Queens I

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example, there exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
 ]

 boolean ok(int[] queens, boolean [] arranged_cols, int row, int col){
        if(arranged_cols[col]==true) return false;
        for(int i=0; i<row; i++){
            if(queens[i] >= 0){
                if(row-i == Math.abs(queens[i]-col)) return false;
            }
        }
    }
    return true;
}
void dfs(List<String[]> boards, int [] queens, boolean[] arranged_cols, int cur_row){
    int n = queens.length;
    if(cur_row==n){
        // generate board
        String board[] = new String[n];
        for(int i=0; i<n; i++){
            StringBuilder row = new StringBuilder();
            for(int j=0; j<n; j++){
                if(j==queens[i]) row.append('Q');
                else row.append('.');
            }
        }
        board[i] = row.toString();
    }
    boards.add(board);
    return;
    }
    for(int col=0; col<n; col++){
        if(ok(queens, arranged_cols, cur_row, col)){
            queens[cur_row] = col;
            arranged_cols[col]=true;
            dfs(boards, queens, arranged_cols, cur_row+1);
            arranged_cols[col]=false;
            queens[cur_row] = -1;
        }
    }
}
public List<String[]> solveNQueens(int n) {
    List<String[]> boards = new ArrayList<String[]>();
    if(n==0) return boards;
    int queens[] = new int[n];
    Arrays.fill(queens, -1);
    boolean arranged_cols[] = new boolean[n];
    dfs(boards, queens, arranged_cols, 0);
    return boards;
}

N Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

Idea:
queens[i]=j => at row i, col j, there is a queen
arranged_cols[i]=true => col i has been placed a queen
for each un-arranged column, iterate each row to check if OK to place a queue

int count = 0;
public boolean ok(int [] queens, boolean [] arranged_cols, int cur_row, int cur_col){
    if(arranged_cols[cur_col]) return false;
    for(int i=0; i<cur_row; i++){
        int j = queens[i]; 
        if(j>=0){
            if(Math.abs(j-cur_col) == cur_row - i) return false;
        }
    }
    return true;
}
public void dfs(int [] queens, boolean [] arranged_cols, int cur_row){
    if(cur_row==queens.length){
        count++;
        return;
    }
    // for each un-arranged column, check each row if it is ok to place a queen
    for(int j=0; j<queens.length; j++){
        if(arranged_cols[j]==false){
            if(ok(queens, arranged_cols, cur_row, j)){
                queens[cur_row] = j;
                arranged_cols[j] = true;
                dfs(queens, arranged_cols, cur_row+1);
                arranged_cols[j] = false;
                queens[cur_row] = -1;
            }
        }
    }
}
public int totalNQueens(int n) {
    if(n<=1) return n;
    // arranged_cols[i] = true in column i, there is a queen
    boolean arranged_cols [] = new boolean [n]; 
    // queens[i] = j means the queen i is placed in column j
    int queens [] = new int [n]; 
    Arrays.fill(queens, -1);
    dfs(queens, arranged_cols, 0);
    return count;
}