题解 | JAVA 递归 #没有重复项数字的全排列# [P3]

没有重复项数字的全排列

http://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1

就暴力递归 + 回溯(省空间)
每次递归, 从小到大(所以一上来要对num进行排序)遍历待选的数,
选到的数从remain中删除,并插入perm中。

O(n!) O(n!)
import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
      // sort just to insure output in alphabet order
      Arrays.sort(num);
      // copy sorted nums to remain
      ArrayList<Integer> remain = new ArrayList<>();
      for (int n : num) remain.add(n); 
      
      permuteRec(remain, new ArrayList<>());
      return ans;
    }
  
    public void permuteRec(ArrayList<Integer> remain, ArrayList<Integer> perm) {
      // base case, i.e. no remaining elem
      if (remain.isEmpty()) {
        // 存答案时必须存copy, 不然之后的回溯会overwrite存入的答案。
        ans.add(new ArrayList<>(perm));
        return;
      }
      
      for (int i = 0; i < remain.size(); i++) {
        Integer a = remain.remove(i);
        perm.add(a);
        permuteRec(remain, perm);
        
        // 复原 (a.k.a 回溯)
        remain.add(i, a);
        perm.remove(perm.size()-1);
      }
    }
}
全部评论

相关推荐

黑皮白袜臭脚体育生:简历条例统一按使用了什么技术实现了什么功能解决了问题或提升了什么性能指标来写会好些,如使用布隆过滤器实现了判断短链接是否存在,大大提升了查询速度
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务