理解和熟悉递归中的尝试

递归的代码不要尝试去展开，它是需要一些自然智慧去理解的，并且是一个逐步尝试和改进的过程。

一、打印n层汉诺塔从最左边移到左右边的全部过程

相信这个问题，大家都已经很熟悉了，但是里面的细节我们还是有必要去学习的。

这个问题的本身，可以理解为从汉诺塔的最左边的柱子的n-1个盘移到中间，然后再将最后一个盘移到最右边，再把中间的n-1个盘全部移到右遍。

在n-1个盘子向中间移动的情况下，最右边的柱子相当于是“其它的”，跟他没有半毛钱关系。而最下面的盘子移到最左边的柱子情况下，中间的柱子相当于是“其他的”，那么就可以分解为下面代码中的func方法：

public class Hanoi {
    
    public static void hanoi(int n) {
    
        if (n > 0) {
    
            func(n, "left", "right", "mid");
        }
    }

    public static void func(int N, String from, String to, String other) {
    
        if (N == 1) {
    
            System.out.println("Move 1 from " + from + " to " + to);
            return;
        }
        func(N - 1, from, other, to);
        System.out.println("Move " + N + " from " + from + " to " + to);
        func(N - 1, other, to, from);

    }

    public static void main(String[] args) {
    
        int n = 3;
        hanoi(n);
    }
}

二、打印一个字符串的全部子序列

我们可以把获取所有子序列的步骤分为两个过程。前提与分析：先设置一个索引index。因为是获取所有的子序列，当遍历到s的index位置下的字符时，我们有权需要这个字符来组成序列或者不需要。因此就有了下面的思路。

public class PrintAllSubsquences {
    
    public static List<String> subs(String s) {
    
        char[] str = s.toCharArray();
        List<String> ans = new ArrayList<>();
        String path = "";
        process1(ans,0,str,path);
        return ans;
    }

    private static void process1(List<String> ans, int index, char[] str, String path) {
    
        if(index==str.length) {
    
            ans.add(path);
            return;
        }
        process1(ans,index+1,str,path);
        process1(ans,index+1,str,path+String.valueOf(str[index]));
    }
}

三、打印一个字符串的不重复的子序列

跟第二个问题差不多，但这里先是拿HashSet来对结果进行保存，过滤掉重复的子序列，再在最后获取到所有的子序列返回即可，这个比较简单。

//列出一个字符串的无重复的子序列 如acc，不重复的子序列为""、a、ac、c、cc、acc
    public static List<String> subsNoRepeat(String s) {
    
        HashSet<String> set = new HashSet<>();
        List<String> ans = new ArrayList<>();
        char[] str = s.toCharArray();
        String path = "";
        process2(0,path,str,set);
        for(String cur:set) {
    
            ans.add(cur);
        }
        return ans;
    }

    private static void process2(int index, String path, char[] str, HashSet<String> set) {
    
        if(index==str.length) {
    
            set.add(path);
            return;
        }
        process2(index+1,path,str,set);
        process2(index+1,path+String.valueOf(str[index]),str,set);
    }

四、打印一个字符串的全部排列

思路有两种：
第一种，因为是打印字符串的全部排列，那么就设计到所有字母都要进行排列。那么就可以采用遍历加递归的形式对其进行排列，被人们称为回溯。

rest数组意思是，在所有字符中，还有多少个字符还没被选中。前面已经选中的就已经固定在path当中了，rest里面的字符的未被选中的就可以进行选择。

最主要的是不要忘了再把当前字符remove后要恢复现场。如果不恢复现场后面就会少字符。

public static List<String> permutation1(String s) {
    
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
    
            return ans;
        }
        char[] str = s.toCharArray();
        List<Character> rest = new ArrayList<>();
        for (char ch : str) {
    
            rest.add(ch);
        }
        String path = "";
        f(rest, ans, path);
        return ans;
    }

    private static void f(List<Character> rest, List<String> ans, String path) {
    
        if (rest.isEmpty()) {
    
            ans.add(path);
            return;
        }
        for (int i = 0; i < rest.size(); i++) {
    
            char cur = rest.get(i);
            rest.remove(i);
            f(rest, ans, path + cur);
            rest.add(i, cur);
        }
    }

第二种思路是，让字符串里面的字符进行两两交换。第一次的时候传入index，即从字符串的哪一个位置进行交换。交换后就可以组成一个新的字符串，保存。

但是不要忘了在进行字符串的保存后，要将交换后的字符串交换回去来恢复现场。

public static List<String> permutation2(String s) {
    
        char[] str = s.toCharArray();
        List<String> ans = new ArrayList<>();
        g1(ans,str,0);
        return ans;
    }

    private static void g1(List<String> ans, char[] str, int index) {
    
        if(index==str.length) {
    
            ans.add(String.valueOf(str));
            return;
        }
        for(int i=index;i<str.length;i++) {
    
            swap(str,i,index);
            g1(ans,str,index+1);
            swap(str,i,index);
        }
    }

    public static void swap(char[] str,int i,int index) {
    
        char tmp = str[i];
        str[i]=str[index];
        str[index]=tmp;
    }

五、打印一个字符串的全部排列，要求不要出现重复的排列

这里我们只需要将第四节的代码进行稍微的修改即可。创建一个数组来判断之前是否有进行相同的剪枝，如果有就跳过不进行分枝。

public static List<String> permutation3(String s) {
    
		List<String> ans = new ArrayList<>();
		if (s == null || s.length() == 0) {
    
			return ans;
		}
		char[] str = s.toCharArray();
		g2(str, 0, ans);
		return ans;
	}

	public static void g2(char[] str, int index, List<String> ans) {
    
		if (index == str.length) {
    
			ans.add(String.valueOf(str));
		} else {
    
			boolean[] visited = new boolean[256];
			for (int i = index; i < str.length; i++) {
    
				if (!visited[str[i]]) {
    
					visited[str[i]] = true;
					swap(str, index, i);
					g2(str, index + 1, ans);
					swap(str, index, i);
				}
			}
		}
	}

	public static void swap(char[] chs, int i, int j) {
    
		char tmp = chs[i];
		chs[i] = chs[j];
		chs[j] = tmp;
	}