leetCode 046 全排列

leetCode 046 全排列

题目描述：

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例输入输出：

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路：

回溯算法（dfs）

利用深度优先算法，将数据遍历，当数据长度达到nums的长度时，说明已经遍历过一次，记录下来。
参数：
- 记录所有答案的数组res；临时答案数组tempList；记录是否已经使用的数组visited。
流程：
- 初始化res、visited，回溯。
- 回溯流程：
  - 结束条件：
    - 判断tempList的长度是否等于nums.length如果是，将tempList加入结果集，结束递归。
  - 要做的事：
    - 建立一个for循环：
      - 将nums的每个元素分别加入temp中。
      - 如果元素位置的visited已被标记为true，遍历下一个。
      - 没有被标记，则在visited标记此数。
      - tempList加入此数。
      - 递归。
      - 将visited的标记去掉。
      - 从temp中将此数移除。
复杂度分析：
- 时间复杂度：O（n*n！）
- 空间复杂度：O（n）
代码：

class Solution {
  public List<List<Integer>> permute(int[] nums) {
      List<List<Integer>> res = new ArrayList<>();
      boolean[] visited = new boolean[nums.length];
      backtrack(res, new ArrayList<>(), nums, visited);
      return res;
  }

  private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, boolean[] visited){
      if(tempList.size() == nums.length){
          list.add(new ArrayList<>(tempList));
      }
      for(int i = 0; i < nums.length; i++){
          if(visited[i] == true) continue;
          visited[i] = true;
          tempList.add(nums[i]);
          backtrack(list, tempList, nums, visited);
          visited[i] = false;
          tempList.remove(tempList.size() -1);
      }
  }
}