332. 重新安排行程

一 题目：

二 思路：

• 本题，从a出发的时候可能会去多个方向，方向不同有不一样的路径，比如这个JFK有俩方向
  

  因此需要用回溯

• 一个票只能用一次，因此我们需要记录一下哪个票用过

三 代码：

  //路径顺序
    List<String> path=new LinkedList<>();
    //票使用顺序
    List<List<String>> res = new LinkedList<>();
    //used数组用于标记不能重复使用一张票
    boolean[] used = new boolean[301];

    public List<String> findItinerary(List<List<String>> tickets) {
        //先按字典序从小到大排列 降落地
        tickets.sort((o1,o2)->o1.get(1).compareTo(o2.get(1)));
        //起点
        path.add("JFK");
        search(tickets,"JFK");
        return res.get(0);

    }

    //从start开始搜寻路径
    private void search(List<List<String>> tickets, String start) {
        //因为这些航班肯定会有一条路线是正确的
        //所以我们加入path的size如果等于tickets.size()+1说明我们找到路线了
        if (path.size() == tickets.size() + 1) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < tickets.size(); i++) {
            //如果起点是目标起点，且没用过
            if (tickets.get(i).get(0).equals(start) && !used[i]){
                //标记已使用
                used[i]=true;
                //加入终点
                String end = tickets.get(i).get(1);
                path.add(end);
                search(tickets, end);
                //移除该点，继续尝试看看有没有别的可能
                used[i]=false;
                path.remove(path.size()-1);
            }
        }
    }