47. 全排列 II

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

思路：
考虑使用 DFS( Depth-first search 深度优先搜索) 来解决此类问题，很多排列组合相关的问题，都可以通过DFS来解决 ；但要注意去重的问题； 去重需要判断层数对应的索引到将要交换的元素值是否相同，不相同才交换

class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {

        //0. 边界条件处理
        if(nums==null) return null;
        //1.1 定义结果数组
        List<List<Integer>> list = new ArrayList();
        //1.2 数组中没有元素就返回
        if(nums.length==0) return list;
        //2.DFS
        dfs(list,nums,0);
        //3.返回结果
        return list;
    }
    
    //深度优先搜索
    private void dfs(List<List<Integer>> list, int[] nums,int idx) {
      
      //1.一轮遍历结束了
      if(idx==nums.length) {
          List<Integer> result = new ArrayList();
          for(int val : nums) {
              result.add(val);
          }
          list.add(result);
          return;
      }

      //2.枚举每一层的各种可能，求出满足条件的排列
      for(int i = idx;i < nums.length;i++) {

            //保证一个数字在idx位置只能出现一次
            if(isRepeat(nums,i,idx)) continue;
            //某一层可以交换的索引
            swap(nums,i,idx);
            //下一层 自动回溯
            dfs(list,nums,idx+1);
            //还原现场
            swap(nums,i,idx);

      }

    }

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

    //是否重复
    private boolean isRepeat(int[] nums,int i,int idx){
         //检查[idx,i)之间的值是否有相同的
         for(int j = idx; j < i;j++) {
             if(nums[j]==nums[i]) return true;
         }
         return false;
    }

}