C# 使用hashset 代码
public class Solution {
private List<IList<int>> result = new List<IList<int>>();
public IList<IList<int>> FindSubsequences(int[] nums) {
// 子序列不能排序
DFS(new List<int>(), nums, 0);
return result;
}
private void DFS(List<int> subset, int[] nums, int startIndex){
// 至少有两个元素
if (subset.Count >= 2){
result.Add(new List<int>(subset));
}
if (startIndex >= nums.Length) return;
HashSet<int> set = new HashSet<int>();
for (int i = startIndex; i < nums.Length; i++){
// 用hashset去重, 保证不会取重复元素, 如[4, 6, 7, 7], 第一个数取4, 第二个数取第一个7和第二个7是一样的, 所以需要去重, 每层重置hashset
if (subset.Count > 0 && nums[i] < subset[subset.Count - 1] || set.Contains(nums[i])){
continue;
}
set.Add(nums[i]);
subset.Add(nums[i]);
DFS(subset, nums, i + 1);
subset.RemoveAt(subset.Count - 1);
}
}
}
C# 使用数组代替hash 代码
public class Solution {
private List<IList<int>> result = new List<IList<int>>();
public IList<IList<int>> FindSubsequences(int[] nums) {
DFS(new List<int>(), nums, 0);
return result;
}
private void DFS(List<int> subset, int[] nums, int startIndex){
if (subset.Count >= 2){
result.Add(new List<int>(subset));
}
if (startIndex >= nums.Length) return;
// 题目数据范围200
int[] set = new int[201];
for (int i = startIndex; i < nums.Length; i++){
// nums[i]可能出现负数, 加100保证>0
if (subset.Count > 0 && nums[i] < subset[subset.Count - 1] || (set[nums[i] + 100] == 1)){
continue;
}
set[nums[i] + 100] = 1;
subset.Add(nums[i]);
DFS(subset, nums, i + 1);
subset.RemoveAt(subset.Count - 1);
}
}
}