回溯法/解空间树 排列树

• 初始时选择第0索引结点
• 选择第i个元素之后形成的父节点，父节点的孩子结点，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点

package xcrj.kchalgorithm.backtracking;

import java.util.Arrays;

/** * 排列树 * 达到要求的排列，所有元素都在；把那个元素放到第1位，把那个元素放到第2位，依次类推 * <p> * 选择第i个元素之后形成的父节点，父节点的孩子结点，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点 */
public class PermutationTree {
    
    /** * @param xs * @param i * @param len */
    public static void permutationTree(int[] xs, int i, int len) {
    
        // 到达叶子结点输出
        if (i == len) {
    
            System.out.println(Arrays.toString(xs));
        }
        // 到达非叶子结点，生成i结点的所有孩子结点j
        else {
    
            // ！选择第i个元素之后形成的父节点，父节点的孩子结点，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点
            for (int j = i; j < len; j++) {
    
                // 交换，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点
                int temp = xs[j];
                xs[j] = xs[i];
                xs[i] = temp;
                // 深度优先遍历操作孩子结点
                permutationTree(xs, i + 1, len);
                // 交换回来
                int temp2 = xs[j];
                xs[j] = xs[i];
                xs[i] = temp2;
            }
        }
    }

    public static void main(String[] args) {
    
        int[] xs = {
    1, 2, 3};
        permutationTree(xs, 0, xs.length);
    }
}