46. Permutations

数组交换元素法

这里的回溯在于：

1. 在前index-1个元素的位置有确定的情况下

2. index 这个位置，可以由index->nums.length的每个位置的元素担任

   1. 所以用一个for循环来把各个元素换到index这个位置上

      class Solution {
      public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        permute(nums, 0, result);
        return result;
      }
      private void permute(int[] nums,  int index, List<List<Integer>> result) {
        if(index == nums.length) {
            result.add(convertArrayToList(nums));
        } else {
            for(int i = index; i < nums.length; i++) {
                swap(nums, index, i);
                permute(nums, index + 1, result );
                swap(nums, index, i);
            }
        }
      }
      private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
      }
      private List<Integer> convertArrayToList(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for(int i : nums) {
            list.add(i);
        }
        return list;
      }
      }

子集添加元素法

1. 新建一个子集

2. 回溯法，每次往子集里面加一个之前没加过的元素

   class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        permute(nums, new ArrayList<>(), result);
        return result;
    }
    private void permute(int[] nums, List<Integer> subSet, List<List<Integer>> result) {
        if(subSet.size() == nums.length) {
            result.add(new ArrayList<>(subSet));
        } else {
            for(int i = 0; i < nums.length; i++) {
                if(!subSet.contains(nums[i])) {
                    subSet.add(nums[i]);
                    permute(nums, subSet, result);
                    subSet.remove(subSet.size()-1);
                }
            }
        }
    }
   }