LeetCode-46-Permutations

LeetCode-46-Permutations

题目描述：

链接：https://leetcode-cn.com/problems/permutations/

思路分析：

这道题也是用回溯算法，但是和子集这道题还有点差别。其实这道题可以看做是对一个树进行遍历，类似下图：

与子集不同的是，这个是每个样本点都需要取到，也就是说，每次递归遍历的时候，起点都为零，那么有：

private void back(List<Integer> tmp, int[] nums) {
      if(tmp.size() == nums.length) {
          ans.add(new ArrayList(tmp));
          // return;
      }
      for(int i = 0; i < nums.length; i++) {
          tmp.add(nums[i]);
          back(tmp,nums,visited);
          tmp.remove(tmp.size()-1);
      }
  }

同时，每个点都只能取一次，需要怎么去做呢？我这里，搞一个表，也就是visited数组，访问过了，就置true，然后回溯的时候置false。

private void back(List<Integer> tmp, int[] nums,boolean[] visited) {
        if(tmp.size() == nums.length) {
            ans.add(new ArrayList(tmp));
            // return; 可以return，也可不，后面有遍历的i < nums.length限制
        }
        for(int i = 0; i < nums.length; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            tmp.add(nums[i]);
            back(tmp,nums,visited);
            visited[i] = false;
            tmp.remove(tmp.size()-1);
        }
    }

至此，回溯函数就写完了。

代码：

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        back(new ArrayList<>(),nums,visited);
        return ans;
    }

    private void back(List<Integer> tmp, int[] nums,boolean[] visited) {
        // if(start == nums.length) {
        //     return;
        // }
        if(tmp.size() == nums.length) {
            ans.add(new ArrayList(tmp));
            // return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            tmp.add(nums[i]);
            back(tmp,nums,visited);
            visited[i] = false;
            tmp.remove(tmp.size()-1);
        }
    }
}

AC记录：

赏

谢谢你请我吃糖果