重新安排行程-332

力扣（LeetCode） 链接：https://leetcode.cn/problems/combination-sum/

解题

/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function(tickets) {
    const result = ['JFK'];
    const map = {};
    //获得map
    for(const ticket of tickets) {
        const [from, to] = ticket;
        if(!map[from]) {
            map[from] = [];
        }
        map[from].push(to);
    }

    //对到达地进行字典排序
    for(const city in map) {
        map[city].sort();
    }

    const backtracking = function() {
        //result元素数量与机票数加1相等表示找到有效行程
        if(result.length === tickets.length +　1) {
            return true;
        }
        //没有从result[result.length - 1]出发的机票
        //或者从result[result.length - 1]出发的机票已被使用过
        if(!map[result[result.length - 1]] || map[result[result.length - 1]].length === 0) {
            return false;
        }
        for(let i = 0; i < map[result[result.length - 1]].length; i++) {
            const city = map[result[result.length - 1]][i];
            //删除已被获取的到达地
            map[result[result.length - 1]].splice(i, 1);
            result.push(city);
            if(backtracking()) {
                return true;
            }
            //回溯
            result.pop();
            map[result[result.length - 1]].splice(i, 0, city);
        }
    }

    backtracking();
    return result;
};