今日算法之_141_数组中的全部子序列
前言
Github:https://github.com/HealerJean
1、数组中的全部子序列
给定一个整型数组, 你的任务是找到所有该数组的子序列,子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
1.1、解题思路
有点像全排列和组合求和
1.2、算法
public void dfs(int index, int[] nums, List<List<Integer>> res, LinkedList<Integer> linkedList, boolean[] used) {
//每次进来都会放进来,不会retrun,一直到全部进入
if (linkedList.size() > 1) {
res.add(new ArrayList<>(linkedList));
}
for (int i = index; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;//下面+1,所以肯定不会有和当前i重复使用
linkedList.add(nums[i]);
dfs(i + 1, nums, res, linkedList, used);
linkedList.removeLast();
used[i] = false;
}
}
1.3、测试
@Test
public void test(){
int[] nums = {4, 6, 7, 7};
System.out.println(findSubsequences(nums));
}