回溯法求解

题目描述输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

最简单直白的做法是排列出所有可能的数字，然后选出其中最小的那一个数作为返回结果。涉及到穷举出所有可能的排列结果，当然就采用回溯法求解。

    public  String PrintMinNumber(int [] numbers) {
        if (numbers == null || numbers.length == 0) {
            return null;
        }
        if (numbers.length == 1) {
            return String.valueOf(numbers[0]);
        }
        //最小值存储变量
        StringBuilder min = new StringBuilder("9999999999999999999999999999999");
        //标记数组，标记数组中元素是否有被访问过
        boolean[] visited = new boolean[numbers.length];
        backing(numbers, new LinkedList<Integer>(), min, visited);
        return min.toString();
    }

    /**
     * 回溯函数：穷举出数组元素所有可能组成的数字
     * @param numbers
     * @param path  路径，存储选择的一个结果
     * @param min
     * @param visited
     */
    private  void backing(int[] numbers, LinkedList<Integer> path, StringBuilder min, boolean[] visited) {
        //当路径变量长度等于数组长度，表示已经用数组所有元素排列出了一个可能结果。判断他与最小值之间的大熊啊关系进行处理
        if (path.size() == numbers.length) {
            String tem = "";
            for (int i = 0; i < path.size(); i++) {
                tem += path.get(i);
            }
            if (tem.compareTo(min.toString()) < 0) {
                min.delete(0, min.length());
                min.append(tem);
            }
        }
        //回溯函数的关键部分：路径的选择。
        //由于是全排列，每次都是从0开始，只要为访问过，就可以再次加入路径变量中
        for (int i = 0; i < numbers.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            path.add(numbers[i]);
            backing(numbers, path, min, visited);
            visited[i] = false;
            path.removeLast();
        }
    }