largest-divisible-subset

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a set of distinct positive integers <code>nums</code>, return the largest subset <code>answer</code> such that every pair <code>(answer[i], answer[j])</code> of elements in this subset satisfies:

<ul>
	<li><code>answer[i] % answer[j] == 0</code>, or</li>
	<li><code>answer[j] % answer[i] == 0</code></li>
</ul>

If there are multiple solutions, return any of them.

&nbsp;
Example 1:

<pre>
Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.
</pre>

Example 2:

<pre>
Input: nums = [1,2,4,8]
Output: [1,2,4,8]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 2 * 109</code></li>
	<li>All the integers in <code>nums</code> are unique.</li>
</ul>

largestDivisibleSubset

Largest Divisible Subset

Array

Math

Dynamic Programming

Sorting

给你一个由 无重复 正整数组成的集合 <code>nums</code> ，请你找出并返回其中最大的整除子集 <code>answer</code> ，子集中每一元素对 <code>(answer[i], answer[j])</code> 都应当满足：
<ul>
	<li><code>answer[i] % answer[j] == 0</code> ，或</li>
	<li><code>answer[j] % answer[i] == 0</code></li>
</ul>

如果存在多个有效解子集，返回其中任何一个均可。

 

示例 1：

<pre>
输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。
</pre>

示例 2：

<pre>
输入：nums = [1,2,4,8]
输出：[1,2,4,8]
</pre>

 

提示：

<ul>
	<li><code>1 <= nums.length <= 1000</code></li>
	<li><code>1 <= nums[i] <= 2 * 109</code></li>
	<li><code>nums</code> 中的所有整数 互不相同</li>
</ul>