質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.12%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

解決済

combination sumを可読性の高いコードで計算する方法

sequelanonymous
sequelanonymous

総合スコア123

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

2回答

0リアクション

0クリップ

1048閲覧

投稿2021/09/18 05:11

下記の問題を可読性高いコードで解きたいと思っています。1)自分で書いたコードでは、途中まで書くことができましたが、書ききれていません。どう試行錯誤してもこのコードをベースに進んでみても解答にたどり着くことができません。

もし、この書き方からどう展開していっても解決には至らない、根本的に違う明確な理由にお気づきの方いましたら、理由をご教示いただけませんしょうか?

もし、この先こう書いたら正解にたどり着くことできる、というのがあれば、コードベースでご教示いただけませんしょうか?

また、2)backtrakingを用いた解答では、backtrackingを用いて完答しました。こちらの書き方は、コードリーディングがしづらく、「知っていたから解けた」「覚えていたから解けた」、というような解答になります。
未だに、問題文からこの解答にたどり着くステップが思いつくことができません。それを思いつくために、まずは、recurionをつかわずに解答しようと思い、1)自分で書いたコードを書き始めました。

もし、こちらの解答についても、こう理解したらすっと解答できる、というようなコツなどありましたらご教示いただけると助かります。

*backtrackingがなにか、backtrackingは、dfsでtraverseするので再帰つかう、などのテクニック的なところが知りたい、というよりは、下記の問題文からどうやってツリーで探索空間としての表現が思いつくか、それをどう実装に落とし込めるかに気づくことができたか、について知りたいと思っています。

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

39. Combination Sum

1)自分で書いたコード

from collections import deque class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: # [2,3,6,7] # [2,2,2,2] -> [2,2,3] = target # [3,3,3] -> [3,3,2] # [6,6] -> [6,2] -> [6,3] # [7] = target candidates.sort() tmp = deque() output = [] for c in candidates: # 2,3,6 while target > sum(tmp): # [2,2,3,6] tmp.append(c) # [2,2,2,2] -> 8 # [2,2,2,3] -> 9 while target < sum(tmp): # 7 < 7 tmp.popleft() # [2,2,2] # [2,2,3] if sum(tmp) == target: # 6 == 7 output.append(tmp) # [2,2,3] tmp.popleft() return output

2)backtrakingを用いた解答

res = [] def dfs(i, cur, total): # (0, [], 0), (0, [2], 2).... (0, [2,2,2,2], 8)......(1, [2,2,2], 6) if total == target: # 0 == 7, 2 == 7 res.append(cur.copy()) return if i >= len(candidates) or total > target: # 0>=4 or 0>7, 0>=4 or 2>7, 8>7 return cur.append(candidates[i]) # [2,2].....[2,2,3] # currのリストには、足したものたちをいれていく。 dfs(i, cur, total+candidates[i]) #(0, [2], 2),(0, [2,2], 4), ....(0, [2,2,2], 6) ....(1, [2,2,3], 7) cur.pop() # (0, [2,2,2,2], 8) -> (0, [2,2,2], 6) dfs(i+1, cur, total) # (1, [2,2,2], 6) dfs(0, [], 0) return res

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.12%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。