46.Permutations

This question on LeetCode is the similar question I solved during a live coding interview this week. After that, I took some time to review BFS and DFS. I believe this is a good opportunity to gain a more extensive understanding of them.

BFS & DFS

They both are the algorithm that begins at the root node and then them explore each node to traverse graphs or trees basically.

Breadth-First Search (BFS)

• Also called it as the Level Order Tree Traversal
• We use a queue to implement BFS
• Traverses a graph level-wise

Depth-First Search (DFS)

• We use a stack to implement DFS
• Traverses a graph depth-wise
• There are different types of DFS traversals
  • In-Order (Left -> Root -> Right)
  • Pre-Order (Root -> Left -> Right)
  • Post-Order (Left -> Right -> Root)

BFS & DFS Sample Code:

public class Traverse {
    public static void main(String[] args) {
        TreeNode root = createSampleTree();

        System.out.println("Dfs for Level Order");
        levelOrderDfs(root);

        System.out.println("Dfs for PreOrder");
        preOrderDfs(root);
        System.out.println();

        System.out.println("Dfs for InOrder");
        inOrderDfs(root);
        System.out.println();

        System.out.println("Dfs for PostOrder");
        postOrderDfs(root);
        System.out.println();

        System.out.println("Bfs for Level Order");
        levelOrderBfs(root);
    }
    //     1
    //    / \
    //   2   3
    //  / \ / \
    //  4 5 6 7
    public static TreeNode createSampleTree() {
        TreeNode root = new TreeNode(1);
        int i = 2;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(i < 8) {
            TreeNode poll = queue.poll();
            if(poll != null) {
                TreeNode left = new TreeNode(i++);
                poll.left = left;
                TreeNode right = new TreeNode(i++);
                poll.right = right;

                queue.add(left);
                queue.add(right);
            }
        }

        return root;
    }
    //Level order traversal
    public static void levelOrderBfs(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            System.out.print(poll.value + " ");

            if(poll.left != null) {
                queue.add(poll.left);
            }
            if(poll.right != null) {
                queue.add(poll.right);
            }
        }
        System.out.println();
    }

    public static void preOrderDfs(TreeNode root) {
        if(root == null) {
            return;
        }

        System.out.print(root.value + " ");
        preOrderDfs(root.left);
        preOrderDfs(root.right);
    }

    public static void inOrderDfs(TreeNode root) {
        if(root == null) {
            return;
        }

        inOrderDfs(root.left);
        System.out.print(root.value + " ");
        inOrderDfs(root.right);
    }

    public static void postOrderDfs(TreeNode root) {
        if(root == null) {
            return;
        }

        postOrderDfs(root.left);
        postOrderDfs(root.right);
        System.out.print(root.value + " ");
    }

    public static void levelOrderDfs(TreeNode root) {
        if(root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            System.out.print(pop.value + " ");

            if(pop.right != null) {
                stack.push(pop.right);
            }
            if(pop.left != null) {
                stack.push(pop.left);
            }
        }
        System.out.println();
    }
}

class TreeNode {
    public Integer value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {}

    public TreeNode(Integer value) {
        this.value = value;
    }
}

Console:

Dfs for Level Order
1 2 4 5 3 6 7 
Dfs for PreOrder
1 2 4 5 3 6 7 
Dfs for InOrder
4 2 5 1 6 3 7 
Dfs for PostOrder
4 5 2 6 7 3 1 
Bfs for Level Order
1 2 3 4 5 6 7 

Question

Solution

We have to traverse all possible combinations, so we can use the recursive backtracking approach to sovle this question step by step following.

1. First we can define a private recursive method helper that takes two arguments that one is the input array nums, and the other is a list list that represents the current permutation.
2. In the helper method, check if the length of list is equal to the length of nums. If so, we have generated a complete permutation and we add a copy of list to the res list. Otherwise, for each element in nums, check if it has already been included in the current permutation. If not, add it to list, recursively call helper with the updated list, and remove the last element from list before proceeding to the next iteration.
3. Therefore, We can call the helper method with an empty list as the starting permutation.

// O(n!)
class Solution {
    private List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list = new ArrayList<>();
        helper(nums, list);
        return res;
    }
    private void helper(int[] nums, List<Integer> list) {
        if(nums.length == list.size()) {
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i=0;i<nums.length;i++) {
            if(!list.contains(nums[i])) {
                list.add(nums[i]);
                helper(nums, list);
                list.remove(list.size()-1);
            }
        }
    }
}

Steps of Recursive