19 Nov 2016

Recursion tree and recursion tree traversal I

文章欢迎转载,但转载时请保留本段文字,并置于文章的顶部
Author: derek0883@gmail.com
本文原文地址:http://www.gorecursion.com/algorithm/2016/11/19/recursion-tree1.html

This article will show you how to using recursion tree to analysis problem, and how to traverse through the tree to get all result we needed. Before you using recursion tree to solve practical problem, you have to learn basic graph concept. Here is very good material for you. http://algs4.cs.princeton.edu/40graphs/

Subsets

Leetcode Subsets

Given a set of distinct integers, nums, return all possible subsets. Note: 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],
  []
]

Video explanation

DFS solution

private List<List<Integer>> dfs(int[] nums) {
    List<List<Integer>> all = new ArrayList<>();
    List<Integer> one = new ArrayList<Integer>();
    dfs(nums, 0, one, all);
    return all;
}
private void dfs(int[] nums, int pos, List<Integer> one, List<List<Integer>> all) {
    if (pos == nums.length) {
        all.add(new ArrayList<Integer>(one));
        return;
    }
    dfs(nums, pos+1, one, all); 
    one.add(nums[pos]);
    dfs(nums, pos+1, one, all); 
    one.remove(one.size()-1);
}

BFS solution

Again BFS requires an auxiliary data structure to keep tracking each node.

class Node {
    ArrayList<Integer> one;
    int idx;
    Node() {one = new ArrayList<Integer>();}
    Node(int i) { idx = i; }
}
private List<List<Integer>> bfs(int[] nums) {
    Queue<Node> q = new LinkedList<>();
    List<List<Integer>> all = new ArrayList<>();
    q.offer(new Node());
    while (!q.isEmpty()) {
        Node n = q.poll();
        if (n.idx == nums.length) {
            all.add(n.one);
        } else {
            Node n1 = new Node(n.idx+1);
            n1.one = new ArrayList<Integer>(n.one);
            n1.one.add(nums[n.idx]);
            // reuse this Node
            n.idx++;
            q.offer(n);
            q.offer(n1);
        }
    }
    return all;
}

Non-recursive DFS solution

private List<List<Integer>> nonRecursiveDfs(int[] nums) {
    Stack<Node> st = new Stack<Node>();
    List<List<Integer>> all = new ArrayList<>();
    st.push(new Node());
    while (!st.isEmpty()) {
        Node n = st.pop();
        if (n.idx == nums.length) {
            all.add(n.one);
        } else {
            Node n1 = new Node(n.idx+1);
            n1.one = new ArrayList<Integer>(n.one);
            n1.one.add(nums[n.idx]);
            n.idx++;
            st.push(n);
            st.push(n1);
        }
    }
    return all;
}