回溯法/解空间树 排列树

    初始时选择第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);
    }
}

时间复杂度

O ( n ! ) O(n!) O(n!) 第0层 第1层:第1位有n种选择 第2层:第2位有n-1种选择(第1位的数字已经确定) 第3层:第3位有n-2种选择 … 第n层:第n位有1种选择

要得到1个完整的排列,从根到叶子一步步完成,所以时间复杂度是 O ( n ! ) O(n!) O(n!)

经验分享 程序员 微信小程序 职场和发展