leetcode:46. 全排列 淡淡的烟草味﹌ 2022-04-11 04:20 177阅读 0赞 ## 题目: ## 给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: \[1,2,3\] 输出: \[ \[1,2,3\], \[1,3,2\], \[2,1,3\], \[2,3,1\], \[3,1,2\], \[3,2,1\] \] ## 分析: ## 深搜加回溯即可,重点是如何回溯,这里参考别人代码选择使用boolean数组 ## 代码: ## public List<List<Integer>> permute(int[] nums) { // 构建结果集 List<List<Integer>> res = new ArrayList<>(); List<Integer> list = new ArrayList<>(); // 记录每一位数字是否被加进去过 boolean[] flag = new boolean[nums.length]; // 深搜 dfs(res, list, nums, flag, 0); return res; } private void dfs(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] flag, int depth) { if (depth == nums.length) { res.add(new ArrayList<Integer>(list)); } else { for (int i = 0; i < nums.length; i++) { // 如果flag[i]为false代表该位数字没被加进去,则往里加入 if (!flag[i]) { list.add(nums[i]); flag[i] = true; dfs(res, list, nums, flag, depth + 1); list.remove(list.size() - 1); flag[i] = false; } } } } ## 效率: ## ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70] ## 总结: ## 深搜加回溯,常规做法 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]: /images/20220411/d13ad5dc82db458ebb47194560d10212.png
还没有评论,来说两句吧...