LeetCode -- Subsets
题目描述：
Given a set of distinct integers, nums, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
求一个集合的所有子集。
这个题目是学习backtracking一道不错的入门题，直接使用回溯结构来解就可以了。需要注意的是，每次添加结果时要对当前子集的元素进行升序排序。
实现代码：
Given a set of distinct integers, nums, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
求一个集合的所有子集。
这个题目是学习backtracking一道不错的入门题，直接使用回溯结构来解就可以了。需要注意的是，每次添加结果时要对当前子集的元素进行升序排序。
实现代码：
public class Solution {
public IList<IList<int>> Subsets(int[] nums)
{
var result = new List<IList<int>>();
Do(nums, 0, new List<int>(), ref result);
return result;
}
private void Do(int[] nums, int start, List<int> current ,ref List<IList<int>> result)
{
result.Add(new List<int>(current.OrderBy(x=>x)));
if(current.Count == nums.Length)
{
return;
}
for(var i = start; i < nums.Length; i++){
current.Add(nums[i]);
Do(nums, i + 1, current, ref result);
current.Remove(current.Last());
}
}
}