The full array is a classic application of DFS. It is often asked whether in daily work or in interviews. Let’s explore this question together.

Topic describes

Their thinking

DFS(depth-first traversal) is used to iterate through one path and then another. DFS is implemented by using an used object to record whether the target element has been traversed.

var permute = function(nums) {
    const result = [];
    const used = {};
    
    function dfs(paths) {
        if (paths.length === nums.length) {
            result.push(paths.slice());
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            paths.push(nums[i]);
            paths
            used[i] = true;
            dfs(paths);
            paths.pop();
            used[i] = false;
        }
    }
    
    dfs([])
    return result;
};
Copy the code

The title to reflect

  • At the heart of the DFS implementation is the use of an object to record whether the target element has been traversed.
  • After DFS traverses a path, it is necessary to remove the top of the stack element from the path array and then place that element in the untraversed state.