Problem 3 Permutation I母题

Method 1 (只对combination有效)不能不加，只能加，一个一个加

High Level

• 什么是一个解？一个permutation

• 如何构造一个解？

  • 每一层：加一个元素进来

  • 分支：这一层所有可以加的元素中，你加谁呀？

  • 在哪收集解（对比subset）：所有元素都contains进来才行

注意

• All Path problem里，我们不允许同一个node在同一个path上使用多次，但是我们允许同一个node在不同path上使用多次

• Q我怎么知道我加这个元素没有？

Implement 1

TC& SC: O(n! * n), O(n)

public List<List<Integer>> permutation(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return result;
    }
    List<Integer> current = new ArrayList<>();
    backTracking(result, nums, current, 0);
    return result;
}
// index：当前层我要固定的位置是谁：层数的信息
private void backTracking(List<List<Integer>> result, int[] nums, List<Integer> current, int index) {
    if (index == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // method 1: O(n) time to check current 里面是不是有nums[i], list: contains(val), O(n)
        if (!current.contains(nums[i])) {
            current.add(nums[i]);
            backTracking(result, nums, current, index + 1);
            current.remove(current.size() - 1);
        }
    }
}

Implement 2

Use Case:

• 我想知道某一个Character我在之前加过没加过==> loop up operation ==> set

• Set<Integer> elementAddedSoFarInPreviousLevel

• 注意，这是对不同层之间纵向的去重，所以应该在不同层之间传递，一定是在主函数创建

这个代码可以跑过所有的test case，但是稳挂，因为这个没办法对付去重？？

public List<List<Integer>> permutation(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return result;
    }
    Set<Character> elementAddedSoFar = new HashSet<>();
    List<Integer> current = new ArrayList<>();
    backTracking(result, nums, current, 0, elementAddedSoFar);
    return result;
}

// index:当前层我要固定的位置是谁：层数的信息
private void backTracking(List<List<Integer>> result, int[] nums, List<List<Integer>> current, int index, Set<Character> elementAddedSoFar) {
    if (index == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // method 2: O(n) space to check if previous level already used this character
        if (!elementAddedSoFar.contains(nums[i])) {
            elementAddSoFar.add(nums[i]);
            current.add(nums[i]);
            backTracking(result, nums, current, index + 1, elementAddSoFar);
            elementAddSoFar.remove(nums[i]);
            current.remove(current.size() - 1);
        }
    }
}

• 不同层之间的重复是 同一条path 同样index上的元素不能用多次 vs 同样value的元素不能用多次

• 这道题之所以能过是因为这道题没有重复所有才能过，但是意义是不对的，要是有重复元素就错了

public List<List<Integer>> permutation(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return result;
    }
    
//注意这里！！！！！！！！！不是element，而是用index
    Set<Character> indexAddedSoFar = new HashSet<>();
    List<Integer> current = new ArrayList<>();
    backTracking(result, nums, current, 0, indexAddedSoFar);
    return result;
}

// index:当前层我要固定的位置是谁：层数的信息
private void backTracking(List<List<Integer>> result, int[] nums, List<List<Integer>> current, int index, Set<Character> indexAddedSoFar) {
    if (index == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // method 2: O(n) space to check if previous level already used this character
        if (!indexAddedSoFar.contains(i)) {
            indexAddedSoFar.add(i);
            current.add(nums[i]);
            backTracking(result, nums, current, index + 1, indexAddedSoFar);
            indexAddedSoFar.remove(i);
            current.remove(current.size() - 1);
        }
    }
}

Method 2 swap swap

• 既不需要O(n)的时间，也不需要O(n)的空间

• High Level 保持不变：通过swap-swap的方式来固定一个元素

• 利用区间O(1)知道哪些元素不能用，哪些元素还没用过可以固定过来

  • [0, index - 1)固定好的元素

  • [index, nums.length - 1] 还没背固定过的，可以用来被固定过来的元素

List Version

public List<List<Integer>> permutation(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return result;
    }
    backTracking(result, nums, 0);
    return result;
}
// level: index: 当前层我正要固定那个index
// [0, index - 1]已经固定好的元素 不能用
// [index, nums.length - 1]可以用来被固定到当前位置的元素

private void backTracking(List<List<Integer> result, int[] nums, int level) {
    if(index == nums.length) {
        List<Integer> current = new ArrayList<>();
        for (int num: nums) {
            current.add(num);
        }
        result.add(current);
        return;
    }
    for (int i = level; i < nums.length; i++) {
        swap(nums, i , level);
        backTracking(result, nums, level + 1);
        swap(nums, i, level);
    }
}
private void swap(int[] nums, int i , int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

String Version

public class Solution {
   public List<String> permutations(String input) {
      // initial the return
     List<String> ret = new ArrayList<String>();
     // transfer input to a curChar
     char[] curChar = input.toCharArray();
    
     // curLevel: the String position
     dfsHelper(0, ret, curChar);
     return ret;
 
   }
 // dfsHelper(curLevel, ret, curChar)
   // corner case
         //if  curLevel reaches the curChar length
         // ret.add(curChar change to the )
         // return
    // iterate the possible position: from curLevel to the curChar.length
       // swap (possiblePostion, curLevel, curChar)
       // dfsHelper(curLevel, ret, curChar)
       // swap (possiblePostion, curLevel, curChar)
   private void dfsHelper(int curLevel, List<String> ret, char[] curChar) {
     if (curLevel == curChar.length) {
       ret.add(new String(curChar));
       return;
     }
     for (int possiblePosition = curLevel; possiblePosition < curChar.length; possiblePosition++) {
       swap(possiblePosition, curLevel, curChar);
       dfsHelper(curLevel + 1, ret , curChar);
       swap(curLevel, possiblePosition, curChar);
     }
   }
   private void swap(int a, int b, char[] curChar) {
     char temp = curChar[a];
     curChar[a] = curChar[b];
     curChar[b] = temp;
   }
  }
 
// TC O(n!)
// SC O(n)