while循环逻辑缺陷

Question

问题如下：给定两个整数 n 和 k，return 1 ... n 中 k 个数字的所有可能组合。

例如，如果 n = 4 且 k = 2，则解为：

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4]
]

我的解决方案是：

public List<List<Integer>> combine(int n, int k) {
    Deque<List<Integer>> queue = new LinkedList<List<Integer>>();
    List<List<Integer>> result = new LinkedList<List<Integer>>();

    for (int i = 1; i <= n; i++) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(i);
        queue.add(list);
    }

    while (!queue.isEmpty()) {
        List<Integer> list = queue.pollFirst();
        if (list.size() == k)
            result.add(list);
        else {
            for (int i = list.get(list.size() - 1) + 1; i <= n; i++) {
                list.add(i);
                queue.addLast(list);
                list.remove(list.size() - 1);
            }
        }
    }
    return result;
}

然而，while 循环进入了无限循环。我不知道逻辑有什么问题。我跟踪了几次，还是找不到这段代码的逻辑漏洞。

Answer 1

你的问题是你多次将同一个列表实例添加到队列中，所以当你写：

            list.add(i); // suppose that list had 1 element. After adding 1,
                         // it has two elements
            queue.addLast(list); // here you add the list with 2 elements to
                                 // the queue
            list.remove(list.size() - 1); // here you remove the added element
                                          // so the list you just added
                                          // to the queue has just 1 element

您添加到队列中的列表保留原始元素数。

您应该在将其添加到队列之前创建一个新的 List 实例：

            list.add(i);
            queue.addLast(new ArrayList<Integer>(list));
            list.remove(list.size() - 1);

Answer 2

以上 while (!queue.isEmpty()) {} 始终为真

while循环逻辑缺陷

While loop logic flaw

java

queue

list

while-loop