【LeetCode】 46. 全排列回溯 JAVA

心已赠人 2021-06-10 20:38 368阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

思考这道题目，很容易想到回溯，理解很容易，如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]  
所以代码写起来，也相对的简单，不过话又说回来，这道题其实不难，还是要多刷一刷题，找到更加合适的解决方案，这个方案依旧不是最优解

### 代码 ###

class Solution { 
        List<List<Integer>> res;
        int[] nums;
        public List<List<Integer>> permute(int[] nums) { 
            this.res = new ArrayList<>();
            this.nums = nums;
            // Arrays.sort(nums); // not necessary
            backtrack(new ArrayList<>());
            return res;
        }
    
        private void backtrack(List<Integer> tempList) { 
            if (tempList.size() == nums.length) { 
                res.add(new ArrayList<>(tempList));
                return;
            }
            for (int i = 0; i < nums.length; i++) { 
                if (tempList.contains(nums[i])) continue;
                tempList.add(nums[i]);
                backtrack(tempList);
                tempList.remove(tempList.size() - 1);
            }
        }
    
    }

[Link 1]: https://leetcode-cn.com/problems/permutations/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/c8adeab4170b480c8fa6607e84575eb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/2a95bcef3ccb4c12b555e0fc2cf85d3c.png