By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

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));
}

​

ContactAuthor