关于leetcode:leetcode-46-Permutations-全排列中等

8次阅读

共计 951 个字符，预计需要花费 3 分钟才能阅读完成。

标签: 搜寻

https://leetcode.cn/problems/permutations

给定一个不含反复数字的数组 nums，返回其所有可能的全排列。你能够按任意程序返回答案。
示例 1：

输出：nums = [1,2,3]
输入：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输出：nums = [0,1]
输入：[[0,1],[1,0]]

示例 3：

输出：nums = [1]
输入：[[1]]

提醒：

1 <= nums.length <= 6
-10 <= nums[i] <= 10

nums 中的所有整数互不雷同

应用回溯法解决此问题，对于每一个以后地位 i，咱们能够将其与之后的任意地位替换，而后持续解决地位 i +1，直到解决到最初一位。为了避免咱们每次遍历时都要新建一个子数组贮存地位 i 之前曾经替换好的数字，咱们就利用回溯法，只对原数组进行批改，在递归实现后再批改回来。

public class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> ans = new ArrayList<>();
      backTracking(nums, 0, ans);
      return ans;
  }

  void backTracking(int[] nums, int level, List<List<Integer>> ans) {if (level == nums.length - 1) {ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
          return;
      }
      for (int i = level; i < nums.length; i++) {
          // 批改以后节点状态
          swap(nums, i, level);
          // 递归子节点
          backTracking(nums, level + 1, ans);
          // 回改以后节点状态
          swap(nums, i, level);
      }
  }

  void swap(int[] nums, int i, int j) {int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
  }
}