程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode -- Permutations

LeetCode -- Permutations

編輯:C++入門知識

LeetCode -- Permutations


題目描述:
Given a collection of 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], and [3,2,1].




就是對給定的數組生成全排列。


思路:
本題主要是Back tracking 的一個基本應用。
1.對於nums的每個元素nums[i] ,i∈[0,n) :
2.拿掉nums[i],對子數組n進行遞歸:
2.1當nums只有兩個元素時,直接返回它們的排列,即{num[0],nums[1]}和{nums[1],nums[0]}
2.2得到遞歸後的子集subSet,遍歷subSet,把拿掉的nums[i]放在子集的第一位
3.把nums[i]放回去




實現代碼:

public class Solution {
    public IList> Permute(int[] nums) {
       return Collect(nums.ToList());
}


private IList> Collect(IList nums)
{
	if(nums.Count <= 1){
		return new List>(){new List(nums)};
	}
	if(nums.Count == 2){
		return new List>(){new List(){nums[0],nums[1]},new List(){nums[1],nums[0]}};
	}
	var newSet = new List>();
	
	for(var i = 0;i < nums.Count; i++){
		// take out nums[i] and put at last for each sub set
		var x = nums[i];
		nums.RemoveAt(i);
		var subSet = Collect(nums);
		for(var k = 0;k < subSet.Count; k++){
			subSet[k].Add(x);
			newSet.Add(subSet[k]);
		}
		nums.Insert(i, x);
	}
	
	return newSet;
}


}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved