LeetCode- 46/47. Permutations/Permutations || (JAVA) (全排列1，2)

46. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,

[1,2,3]

have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
      

全排列沒有重複數字

public class Solution {
	List<List<Integer>> ret = new ArrayList<>();
	List<Integer> tmp = new ArrayList<>();

	public List<List<Integer>> permute(int[] nums) {
		boolean[] vis = new boolean[nums.length];
		dfsCore(nums, 0, nums.length);
		// dfs(nums, 0, nums.length, vis);
		return ret;
	}

	// 使用交換
	private void dfsCore(int[] nums, int idx, int len) {
		if (idx == len) {
			// 找到轉置完成後的解，将其存入清單中
			List<Integer> list = new ArrayList<>();
			for (int i = 0; i < len; i++) {
				list.add(nums[i]);
			}
			ret.add(list);
		} // 将目前位置的數跟後面的數交換，并搜尋解
		for (int i = idx; i < len; i++) {
			swap(nums, idx, i);
			// 傳入idx+1
			dfsCore(nums, idx + 1, len);
			swap(nums, idx, i);

		}
	}

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

public class Solution {
	List<List<Integer>> ret = new ArrayList<>();
	List<Integer> tmp = new ArrayList<>();

	public List<List<Integer>> permute(int[] nums) {
		boolean[] vis = new boolean[nums.length];
		dfs(nums, 0, nums.length, vis);
		return ret;
	}

	// DFS+回溯
	private void dfs(int[] nums, int idx, int len, boolean vis[]) {
		if (tmp.size() == len) {
			ret.add(new ArrayList<>(tmp));
		}
		for (int i = 0; i < len; i++) {
			if (vis[i])
				continue;
			// 遇到已經加過的元素就跳過
			vis[i] = true;
			// 加入該元素後繼續搜尋
			tmp.add(nums[i]);
			// 可以不傳i+1參數，但是遞歸次數增多
			dfs(nums, i + 1, len, vis);
			tmp.remove(tmp.size() - 1);
			vis[i] = false;
		}
	}
}
           

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,

[1,1,2]

have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
      

全排列有重複數字

判斷邏輯也可以，跳過相同循環

if (vis[i] || (i > 0 && nums[i - 1] == nums[i]&& !vis[i - 1]))

                continue;

public class Solution {
	List<List<Integer>> ret = new ArrayList<>();
	List<Integer> tmp = new ArrayList<>();

	public List<List<Integer>> permuteUnique(int[] nums) {
		boolean[] vis = new boolean[nums.length];
		// 排序
		Arrays.sort(nums);
		dfs(nums, 0, nums.length, vis);
		return ret;
	}

	// DFS+回溯
	private void dfs(int[] nums, int idx, int len, boolean vis[]) {
		if (tmp.size() == len) {
			ret.add(new ArrayList<>(tmp));
		}
		for (int i = 0; i < len; i++) {
			if (vis[i])
				continue;
			// 遇到已經加過的元素就跳過
			vis[i] = true;
			// 加入該元素後繼續搜尋
			tmp.add(nums[i]);
			// 可以不傳i+1參數，但是遞歸次數增多
			dfs(nums, i + 1, len, vis);
			tmp.remove(tmp.size() - 1);
			vis[i] = false;
			///
			// 跳過本輪的重複元素，確定每一輪隻會加unique的數字
			while (i < nums.length - 1 && nums[i] == nums[i + 1])
				i++;

		}
	}
}
           

最新測試用例添加了 字典序，此方法不過,

List<List<Integer>> ret = new ArrayList<>();
	List<Integer> tmp = new ArrayList<>();

	public List<List<Integer>> permuteUnique(int[] nums) {
		Arrays.sort(nums);
		dfsCore(nums, 0, nums.length);
		return ret;
	}

	// 使用交換
	private void dfsCore(int[] nums, int idx, int len) {
		if (idx == len) {
			// 找到轉置完成後的解，将其存入清單中
			List<Integer> list = new ArrayList<>();
			for (int i = 0; i < len; i++) {
				list.add(nums[i]);
			}
			ret.add(list);
		} // 将目前位置的數跟後面的數交換，并搜尋解
		for (int i = idx; i < len; i++) {
			/*if (i > idx && nums[i] == nums[i - 1])
				continue;*/

			swap(nums, idx, i);
			// 傳入idx+1
			dfsCore(nums, idx + 1, len);
			swap(nums, idx, i);

			while (i < nums.length - 1 && nums[i] == nums[i + 1])
				i++;
		}

	}

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