LeetCode_ 46_ Full Permutation

Topic link

• https://leetcode.cn/problems/permutations/

Title Description

Give an array without duplicate numbers nums , Back to its All possible permutations . You can In any order Return to the answer .

Example 1：

 Input ：nums = [1,2,3]
 Output ：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2：

 Input ：nums = [0,1]
 Output ：[[0,1],[1,0]]

Example 3：

 Input ：nums = [1]
 Output ：[[1]]

Tips ：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums All integers in Different from each other

Their thinking

backtracking

Note here that it is necessary to record whether a number has been used , Because the title says nums The numbers inside are different from each other , So it can be used path.contains(nums[i]) To determine whether this number has been used

The retrospective trilogy

• Recursive function parameters
  • nums： Given set
  • path： The results of the record meet the conditions of
  • ans： Set of recorded results
• Termination conditions
  • Find the leaves , namely path,size() == nums.length
• Single layer logic
  • Every secondary investment search , Then skip the used numbers

AC Code

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

    private static void backTracing(int[] nums, List<Integer> path, List<List<Integer>> ans) {
    
        if (path.size() == nums.length) {
    
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
    
            if (path.contains(nums[i])) {
    
                continue;
            }
            path.add(nums[i]);
            backTracing(nums, path, ans);
            path.remove(path.size() - 1);
        }
    }
}